# How to prove a number $a$ is quadratic residue modulo $n$?

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.

-
The statement in the box doesn't make sense - certainly, there are quadratic residues modulo $n$ that are coprime to $n$ even when $n$ is not of the form $4\cdot m$ where $m$ is odd. For example, let $n$ be any odd prime. –  Zev Chonoles Apr 6 '11 at 5:44
@Zev Chonoles: Thanks for pointing that out. It should be "If $\alpha =2$, then $a \equiv 1 \pmod{4}$. –  Chan Apr 6 '11 at 5:47

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.

-
Many thanks for the reference. –  Chan Apr 7 '11 at 0:18

Suppose $n=4\cdot m$ where $m$ is odd, and $a\in\mathbb{Z}$ is a quadratic residue modulo $n$ that is coprime to $n$. Thus there is an $x\in\mathbb{Z}$ such that $x^2\equiv a\bmod n$. Because $a$ is coprime to $n$, it must be odd. If $x$ were even, then $x^2$ would be divisible by 4, hence $x^2-a$ could not be divisible by 4, much less $n=4\cdot m$. Thus $x$ must be odd, say $x=2y+1$. Then $$x^2=(2y+1)^2=4y^2+4y+1\equiv a\bmod 4m$$ and thus reducing mod 4, we have that $a\equiv 1\bmod 4$.

-
Thanks, so what do I have to show here? I'm still confusing what do I need to show in order to say $a$ is quadratic residue modulo $n$? –  Chan Apr 6 '11 at 14:52
@Chan - actually Bill's answer gives a more general result, I only proved the boxed statement. However, I'm not sure in general how to determine when $a$ is a QR mod $n$ (i.e., even when $a$ and $n$ are not coprime). –  Zev Chonoles Apr 6 '11 at 23:20
Thanks anyway. Although Bill's answer is great, sometimes it is too advance for me. I tried to understand what he tried to convey, but most of the time I'm lost. –  Chan Apr 6 '11 at 23:27