If p is a prime number and a is prime to p,and if a square number c2 can be found such that c2-a is divisible by p, then show that a(p-1)/2-1 is divisible by p
-
UP 0 DOWN 0 0 2
2 Answers
341This is known as Lagrange's condition for solvability of the quadratic congruence. c^2 \equiv a \pmod p \Rightarrow 1 \equiv c^{p-1} = (c^2)^{\frac{p-1}{2}} \equiv a^{\frac {p-1}{2}} \pmod p When this condition is satisified it is denoted using the Legendre symbol as \left(\frac{a}{p} \right) = 1 and we say that a is a quadratic residue modulo p. In general the equation x^n \equiv a \pmod p has a solution iff a^{\frac{p-1}{b}} \equiv 1 \pmod p where b = gcd (n,p-1)