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

  • $\begingroup$ 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. $\endgroup$ Apr 4, 2011 at 6:22
  • $\begingroup$ @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? $\endgroup$
    – roxrook
    Apr 4, 2011 at 6:26
  • $\begingroup$ 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}$. $\endgroup$ Apr 4, 2011 at 6:29
  • $\begingroup$ 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? $\endgroup$
    – roxrook
    Apr 4, 2011 at 6:30
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2011 at 6:39

1 Answer 1


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.

  • $\begingroup$ Thank you. I will try your way. $\endgroup$
    – roxrook
    Apr 4, 2011 at 6:33
  • $\begingroup$ See here for the number of roots. $\endgroup$ May 26, 2019 at 2:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .