\[a\]
then there exists \[x\]
such that \[x^2 \equiv a \; (mod \; n)\]
. Then \[(x^2)^{\frac{\phi (n)}{2}} =x^{\phi (n)} \equiv 1 \; (mod \; n)\]
by Euler's Theorem, then \[a^{\frac{\phi (n)}{2}} \equiv 1 \; (mod \; n)\]
.It is not true however that if
\[a^{\frac{\phi (n)}{2}} \equiv 1 \; (mod \; n)\]
then \[a\]
is a quadratic residue of \[n\]
.3 is not a quadratic residue of 8 since
\[1^2 =1 \equiv 1 \; (mod \; 8)\]
\[2^2 =4 \equiv 4 \; (mod \; 8)\]
\[3^2 =9 \equiv 1 \; (mod \; 8)\]
\[4^2 =16 \equiv 0 \; (mod \; 8)\]
\[5^2 =25 \equiv 1 \; (mod \; 8)\]
\[6^2 =36 \equiv 4 \; (mod \; 8)\]
\[7^2 =49 \equiv 1 \; (mod \; 8)\]
But
\[2^{\frac{\phi (9)}{2}}=3^4=81 \equiv 1 \; (mod \; 8)\]
so the converse is not the case.