Sunday, 18 March 2018

discrete mathematics - Euclid's lemma, mod, gcd proof


(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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...