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.

  • $\begingroup$ Could you please rewrite it correctly ? $\endgroup$ – Maman Sep 28 '16 at 21:03
  • $\begingroup$ @Maman I think i mostly fixed the formatting. Sorry if it's not entirely correct I'm not sure what the standard is $\endgroup$ – greenteam Sep 28 '16 at 21:26
  • 1
    $\begingroup$ 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. $\endgroup$ – egreg Sep 28 '16 at 21:38
  • $\begingroup$ Ok nice question ! $\endgroup$ – Maman Sep 28 '16 at 21:51
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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)$ $\endgroup$ – greenteam Sep 28 '16 at 23:45
  • $\begingroup$ Please take a look at my answer to this duplicate question. $\endgroup$ – Bernard Sep 29 '16 at 0:15
  • $\begingroup$ @sysgymn what do you think ? More details ? $\endgroup$ – Maman Sep 29 '16 at 17:41
  • $\begingroup$ @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? $\endgroup$ – greenteam Sep 29 '16 at 21:52
  • 1
    $\begingroup$ @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" $\endgroup$ – 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[2][]{\mathbb{Z}/#2_{#1}\mathbb{Z}} \varphi\colon\Z{m}\to \Z[1]{p}\times\Z[2]{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.


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.