Quadratic Residue of a Composite Modulus

If  {jjatex options:inline}a{/jatex}  is a quadratic residues of  
\[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.

Add comment

Security code
Refresh