(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.
No comments:
Post a Comment