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
Best Answer
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.