2
$\begingroup$

Problem

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

  • 0
    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.2011-04-04
  • 0
    @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`?2011-04-04
  • 0
    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}$.2011-04-04
  • 0
    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?2011-04-04
  • 0
    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.2011-04-04
  • 0
    Thanks. The reason that I wrote that $x^2$ is I was try to adapt the theorem from the book. They use $a$ is for every $p_i$, so I think if $a$ could be, why not $x^2$. I consider $x^2$ as a unique number $a$.2011-04-04

1 Answers 1

3

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.

  • 0
    Thank you. I will try your way.2011-04-04