# using Euclid's lemma in mod proof

a) Use Euclid’s Lemma to show that for every odd prime $p$ and every integer $a$, if $a \not\equiv 0 \pmod p$, then $$x^2 \equiv a \pmod p$$ has $0$ or $2$ solutions modulo $p$.

b) Generalize this in the following way:

Let $m = p_1\cdots p_r$ with distinct odd primes $p_1,\dots, p_r$ and let $a$ be an integer with $\gcd(a, m) = 1$. Show that $$x^2 ≡ a \pmod m$$ has either $0$ or $2^r$ solutions modulo $m$.

My attempt at part a is as follows: suppose $$x^2 ≡ a \pmod p$$ $$y^2 ≡ a \pmod p$$ Then $$x^2 ≡ y^2 \pmod p$$ $$x^2 - y^2 ≡ 0 \pmod p$$ $$(x+y)(x-y)≡ 0 \pmod p$$

So now using Euclid's lemma $p \mid (x+y)$ or $p\mid(x-y)$, hence $y ≡ x \pmod p$ or $y ≡ -x \pmod p$

This would mean the two solutions would be $x$ and $-x$ but I'm not sure how to prove that there must be exactly 2 or exactly 0 solutions. Is it sufficient to say that if $x^2 ≡ a \pmod p$ then $(-x^2) ≡ a \pmod p$?

Is it also true and since $x \neq-x$ then there must be two solutions? That also doesn't cover the case of 0 solutions.

• Could you please rewrite it correctly ? – Maman Sep 28 '16 at 21:03
• @Maman I think i mostly fixed the formatting. Sorry if it's not entirely correct I'm not sure what the standard is – greenteam Sep 28 '16 at 21:26
• You have correctly proved that if $x$ is a solution, then another solution is either the same as $x$ or $-x$ (modulo $p$). Since $p$ is an odd prime, $x\not\equiv-x\pmod{p}$ and so either there's no solution or there are two solutions. – egreg Sep 28 '16 at 21:38
• Ok nice question ! – Maman Sep 28 '16 at 21:51
• If you want to use again your technique you will have to prove that for instance $\gcd(p_i, x-y)=1$. Or maybe you can use the CRT. – Maman Sep 28 '16 at 22:07

Let $m=p_1...p_r$ and the equation $x^2\equiv a \pmod m$ with $\gcd(a,m)=1$

Notice that $0$ solution is given by the fact that $a\not\equiv (\pm a')^2\pmod {m}$ ($a$ is not a quadratic residue $\pmod m$ if you prefer).

For each $i\in \{1,...,r\}$ we have $p_i \mid (x-a')$ or $p_i \mid (x+a')$ (it's Euclid's lemma).

For the first case we want to prove that if each $i\in \{1,...,r\},\ p_i \mid (x+a')$ then the product divides also $(x+a')$.

$(p_i)_{i\in\{1,...,r\}}$ are pairwise coprime. Using a contradiction and Euclid's lemma you can deduce that $\gcd(p_2...p_r=P_1,...,p_1...p_{r-1}=P_r)=1$. By Bachet Bezout's generalized identity you have the existence of $u_1,...,u_r\in \mathbb{Z}$ such that : $u_1P_1+...+u_rP_r=1$. by multiplying this identity by $(x+a')$ you get directly the fact that the product divides $(x+a')$.

So you get $(x+a')\equiv 0 \pmod m$ and the other case is similar. But it gives you $2$ solutions. We have just done the two main cases.

And if we consider two systems of CRT system (the one for $a'$ and the other for $-a'$), for each we get a unique solution $\pmod m$ so it finally gives the first two solutions.

Here is the second case : we can consider that $p_k\mid(x+a')$ and $P_k=\frac{1}{p_k}\prod\limits_{i=1}^r p_i\mid (x-a')$ with $\gcd(p_k,P_k)=1$. By the CRT you have the system $x\equiv -a' \pmod {p_k}$ and $x\equiv a' \pmod{P_k}$ and have an unique $x \pmod m$. And you still have the other solution if you reverse $p_k$ and $P_k$. So it gives two solutions.

Then you continue, for instance $p_kp_l \mid (x+a')$ (with $l,r\in\{1,...,r\}$) and $P_k \mid (x-a')$ and $P_l \mid (x-a')$. You clearly have $p_k,p_l,P_k,P_l$ pairwise coprime (if you want to see it you can use Euclid's lemma and contradiction). Moreover the fact that $\gcd(p_k,p_l)=1=\gcd(P_k,P_l)$ by a consequence of Bachet-Bézout identity $p_k\mid (x+a')$ and $p_l \mid (x+a')$ (same for $P_k,P_l$). By the CRT you get a system of four equations which tell you that there exists an unique $x\pmod m$. By reversing you still have 2 solutions.

You can iterate the process and it gives you $2^r$ solutions.

• i'm not quite sure how you got to the second step $$p_i∣(x−a)$$ or $$pi∣(x+a)$$ I understand euclid's lemma but not sure how you used it to get there from $x^2 ≡ a (mod m)$ – greenteam Sep 28 '16 at 23:45
• Please take a look at my answer to this duplicate question. – Bernard Sep 29 '16 at 0:15
• @sysgymn what do you think ? More details ? – Maman Sep 29 '16 at 17:41
• @Maman I'm a bit unclear on the construction of $$gcd(p_2, .. p_r = P_1, ..., p_1, ... (p_r-1)= P_r)$$ ? why go from 2 to r and 1 to r-1? – greenteam Sep 29 '16 at 21:52
• @sysgymn the fact is that you can say directly what the solutions according to the CRT are... But here is a more formal proof I think it's interesting to see that kind of construction instead of calling "by CRT it's finished" – Maman Sep 29 '16 at 22:29

Your proof for (a) is essentially correct. It can be shortened by observing that $\mathbb{Z}/p\mathbb{Z}$ is a field, so a degree two equation has at most two solutions. Since $p$ is an odd prime, the existence of a solution implies that also its negative is a distinct solution. So either no solution or two.

For (b), you can use the fact that the Chinese remainder theorem proves that the map $$\newcommand\Z[]{\mathbb{Z}/#2_{#1}\mathbb{Z}} \varphi\colon\Z{m}\to \Z{p}\times\Z{p}\times\dots\times\Z[r]{p} \qquad [x]_m\mapsto\bigl([x]_{p_1},[x]_{p_2},\dots,[x]_{p_r}\bigr)$$ is a ring isomorphism (where $[x]_n=x+n\mathbb{Z}$).

Thus the existence of a solution for $[x^2]_m=[a]_m$ implies, via projections the existence of a solution for $[x^2]_{p_i}=[a]_{p_i}$ ($i=1,2,\dots,r$).

Conversely, if $[x_i]_{p_i}$ is a solution for $[x^2]_{p_i}=[a]_{p_i}$ in $\Z[i]{p}$, for $i=1,2,\dots,r$, then $$\varphi^{-1}\bigl([x_1]_{p_1},[x_2]_{p_2},\dots,[x_r]_{p_r}\bigr)$$ is a solution for $[x^2]_m=[a]_m$. Hence either there is no solution (because $[x^2]_{p_i}=[a]_{p_i}$ has none for at least one $i$), or we have $2^r$ solutions, by choosing one among the two in each component.