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.

  • $\begingroup$ 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. $\endgroup$ – Zev Chonoles Apr 6 '11 at 5:44
  • $\begingroup$ @Zev Chonoles: Thanks for pointing that out. It should be "If $\alpha =2$, then $a \equiv 1 \pmod{4}$. $\endgroup$ – 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.

  • $\begingroup$ Many thanks for the reference. $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – Chan Apr 6 '11 at 14:52
  • $\begingroup$ @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). $\endgroup$ – Zev Chonoles Apr 6 '11 at 23:20
  • $\begingroup$ 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. $\endgroup$ – Chan Apr 6 '11 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.