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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Prove that $a$ is quadratic residue mod $m$ iff $a$ is quadratic residue mod $p$ for each prime $p$ divides $m$ where $m$ is odd, and $(a, m) = 1$.

My attempt was using this property of congruence:
If $$x^2 \equiv a \pmod{p_1}$$ $$x^2 \equiv a \pmod{p_2}$$ $$ \cdots $$ $$x^2 \equiv a \pmod{p_k}$$

Then $x^2 \equiv a \pmod{p_1 \cdot p_2 \cdots p_k}$

However, if $m = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then I think it is still not enough because now, $p_i$ is raised to a power $a_i$. I checked all the theorems in my book, and I did not find any theorem claims that, if $x^2 \equiv a \pmod{p}$ then $x^2 \equiv a \pmod{p^e}$. In fact, I tried some examples, and it was clearly wrong. So what am I missing in this case to complete this proof? Am I in the right track? Any idea would be greatly appreciated.

Thank you

share|cite|improve this question
Your argument is incorrect because the "$x$" that squares to $a\bmod p_i$ is going to be different for each $i$ - in fact, those $x$'s each live in different rings (the $\mathbb{Z}/p_i\mathbb{Z}$); you're conflating them. – Zev Chonoles Apr 4 '11 at 6:22
@Zev Chonoles: Thanks. I meant $x^2$, sorry for the typo. But I'm not sure I understood your comment because I really don't know what is ring? – Chan Apr 4 '11 at 6:26
No, I meant that you should have written the list of equations as $x_i^2\equiv a\bmod p_i$, where $x_i\in\mathbb{Z}/p_i\mathbb{Z}$. – Zev Chonoles Apr 4 '11 at 6:29
Oh, I see. Thank you. But I don't understand why it has to be $x_i$ though. Could you explain it one more time? – Chan Apr 4 '11 at 6:30
I suppose it would be clearer if we left behind the $\mathbb{Z}/p_i\mathbb{Z}$. Let me say it this way: The statement that $a$ is a QR modulo $b$ is the statement that there exists an $x\in\mathbb{Z}$ such that $x^2\equiv a\bmod b$. If we say that $a$ is a QR for multiple $b$'s, the $x$'s might not be the same - you should indicate this fact. – Zev Chonoles Apr 4 '11 at 6:39
up vote 3 down vote accepted

HINT $\ $ Use the Chinese Remainder Theorem to reduce to the prime power case, and then use Hensel's lemma to reduce to the prime case. In fact, in this manner, one may prove the following generalized Euler criterion.

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|cite|improve this answer
Thank you. I will try your way. – Chan Apr 4 '11 at 6:33

Your Answer


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.