(a) Let p be an odd prime and a be an integer with gcd. 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