(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$.

  • $\begingroup$ is that beacause since its 2 modulo each $p_i$, we'll have $2*2*...*2$ (r times). Hence, $2^r$ ? $\endgroup$ – greenteam Sep 29 '16 at 4:06
  • 1
    $\begingroup$ @sysgymn: It's exactly that. $\endgroup$ – Bernard Sep 29 '16 at 7:31

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.