In general, to show that $a$ is quadratic residue modulo $n$? What do I have to show? I'm always struggling with proving a number $a$ is quadratic residue or non-quadratic residue.
For example,
If $n = 2^{\alpha}m$, where $m$ is odd, and $(a, n) = 1$.
Prove that $a$ is quadratic residue modulo $n$ iff the following are satisfied:
If $\alpha = 2$ then $a \equiv 1 \pmod{4}$.
I just want to know what do I need to show in general, because I want to solve this problem on my own. Any suggestion would be greatly appreciated.
Thank you.
Best Answer
The correct statement is as below. Note that the special case you mention follows from the fact that $\rm\ a = b^2\ (mod\ 4\:m)\ \Rightarrow\ a = b^2\ (mod\ 4)\:,\:$ but $1$ is the only odd square $\rm\:(mod\ 4)\:,\ $ so $\rm\ a\equiv 1\ (mod\ 4)\:$
THEOREM $\ $ Let $\rm\ a,\:n\:$ be integers, with $\rm\:a\:$ coprime to $\rm\:n\ =\ 2^e \:p_1^{e_1}\cdots p_k^{e_k}\:,\ \ p_i\:$ primes.
$\rm\quad\quad \ x^2\ =\ a\ \ (mod\ n)\ $ is solvable for $\rm\:x\:$
$\rm\quad\quad \: \iff\ \ \: a^{(p_i\ -\ 1)/2} \ \ \equiv\ \ 1\ \ (mod\ p_i)\quad\quad\ \ $ for all $\rm\ i\le k$
$\quad\quad\ $ and $\rm\quad\ \ e>1 \:\Rightarrow\: a\equiv 1\ \ (mod\ 2^{2+\delta}\:),\ \ \ \delta = 1\ \ if\ \ e\ge 3\ \ else\ \ \delta = 0$
Proof: See Ireland and Rosen, A Classical Introduction to Modern Number Theory, Proposition 5.1.1 p.50.