Quadratic ResiduesDate: 05/24/2002 at 01:12:19 From: James Subject: Quadratic residue problem How do I solve this following question? Let p be a prime. If a^((p-1)/2) is congruent to 1 modulo p, then show that a is a quadratic modulo p. Thanks for your time! James Date: 05/24/2002 at 09:58:50 From: Doctor Paul Subject: Re: Quadratic residue problem We actually need to assume that the prime p is an odd prime. The proof breaks down otherwise. You'll see where we need this assumption a bit later. Assume that a^((p-1)/2) = 1 mod p. Let x be a primitive root modulo p. We know that at least one such x exists for all primes p. Then there exists an integer t such that x^t = a mod p. Then x^(t*((p-1)/2)) = (x^t)^((p-1)/2) = a^((p-1)/2) = 1 mod p We know that x^(p-1) = 1 mod p and that no smaller power of x is congruent to 1 mod p. Moreover, we know that if x^w = 1 mod p then it must be the case that w is a multiple of (p-1), i.e., w = 0 mod (p-1) Applying this result to the above equation, we obtain: t*((p-1)/2) = 0 mod (p-1) Now, p is an odd prime. Then p-1 is even. Then t*((p-1)/2) is a multiple of the even number (p-1) and must also be even (since any multiple of an even number is even). The only way that t*((p-1)/2) = t/2 * (p-1) can be a multiple of (p-1) is if t/2 is an integer and this happens only when t is even. So t is even and t/2 is an integer. Then (x^(t/2))^2 = x^t = a mod p which shows that a is a quadratic residue mod p [it is the square of the element x^(t/2)]. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/