Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
Many thanks for the reference. –  Chan Apr 7 '11 at 0:18
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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