# Euclid's lemma, mod, gcd proof

(a) Let $p$ be an odd prime and $a$ be an integer with $\gcd(a, p) = 1$. Show that $x^2 - a \equiv 0 \mod p$ has either $0$ or $2$ solutions modulo $p$

b) Generalize Part a) in the following way: Let $m = p_{1} · · · p_{r}$ with distinct odd primes $p_{1} · · · p_{r}$ and let $a$ be an integer with gcd(a, m) = 1. Show that $x_{2} ≡ a \bmod m$ has either $0$ or $2^r$ solutions modulo m.

Answer: (a) If $p=2$, no solution. If $p>2$ and $\gcd(a,p)=1$ and if a solution exists, so will a second solution because $(-x)^2 \equiv x^2\bmod p$ and $-x\not\equiv x \bmod p$.

$(-x)^2\equiv y^2\bmod p$ means $x^2-y^2=(x-y)(x+y)\equiv0\bmod p$. By Euclid's lemma, this implies either $p|x-y$ or $p|x+y$. Therefore, either $y \equiv x\bmod p$ or $y \equiv -x\bmod p$ and there is no possibility of a third solution.

This shows that $x^2\equiv a\bmod p$ either has no solutions or exactly two solutions.

I'm not sure how to do part b though.

By the Chinese remainder theorem: $$\mathbf Z/m\mathbf Z\simeq \mathbf Z/p_1\mathbf Z\times \dots\times \mathbf Z/p_r\mathbf Z\times,$$ so $x^2\equiv a\mod m$, has a solution if and only if it has two modulo each $p_i$.
• is that beacause since its 2 modulo each $p_i$, we'll have $2*2*...*2$ (r times). Hence, $2^r$ ? – greenteam Sep 29 '16 at 4:06