3
$\begingroup$

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.

  • 0
    @Zev Chonoles: Thanks for pointing that out. It should be "If $\alpha =2$, then $a \equiv 1 \pmod{4}$.2011-04-06

2 Answers 2

5

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.

  • 0
    Many thanks for the reference.2011-04-07
1

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$.

  • 0
    Tha$n$ks 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.2011-04-06