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$ – Zev Chonoles Apr 4 '11 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$ – Chan Apr 4 '11 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$ – Zev Chonoles Apr 4 '11 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$ – Chan Apr 4 '11 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$ – Zev Chonoles Apr 4 '11 at 6:39

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$ – Chan Apr 4 '11 at 6:33
  • $\begingroup$ See here for the number of roots. $\endgroup$ – Bill Dubuque May 26 at 2:39

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.