Proof Involving Legendre SymbolDate: 02/03/2003 at 10:01:11 From: Arkadi Subject: p, q are both prime odd numbers prove that (a/p)=(a/q) If p, q are both prime odd numbers such that they are not factors of a, and p=q(mod 4a), prove that (a/p)=(a/q). (a/p) is Legendre's symbol for: {1 if exists b such that b^2=a(mod p); -1 if there is no b such that b^2=a(mod p)} Euler proved that: (a/p)=a^((p-1)/2) (mod p) The reciprocity theorem says that if p, q are both odd numbers such that their gcd is 1, then (p/q)*(q/p) = (-1)^(((p-1)/2)*((q-1)/2)) Date: 02/03/2003 at 11:52:54 From: Doctor Jacques Subject: Re: p, q are both prime odd numbers prove that (a/p)=(a/q) Hi Arkadi, We can start by doing some simplifications. First, note that we can remove any square factor from a, since such a factor leaves the Legendre symbol unchanged. We may therefore assume that a is a product of distinct primes, with possibly a minus sign. By the multiplicative property of the Legendre symbol, it will be enough to prove that: (s/p) = (s/q) where s is any prime factor of a, or -1 if a is negative. Note also that p = q (mod 4a) implies p = q (mod 4s). The trick is to prove the above result separately in three cases: (1) s = -1 (2) s = 2 (3) s is an odd prime. As you should know, there are different criteria in each case for s to be a quadratic residue. I'll let you try to prove these three cases, using the fact that p = q (mod 4s). Do not hesitate to write back if you are still stuck. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 04/14/2003 at 18:44:52 From: Renee Subject: Legendre Symbol This proof makes sense, but I am not sure how to prove the result in the three cases. Could you help me, please? Date: 04/15/2003 at 03:54:16 From: Doctor Jacques Subject: Re: Legendre Symbol Hi Renee, Let us first recall the Quadratic Reciprocity laws: If p and q are odd primes: * (-1/p) = 1 iff p = 1 (mod 4) * (2/p) = 1 iff p = 1 or p = 7 (mod 8)µ * (p/q) = (q/p) if p = 1 or q = 1 (mod 4); (p/q) = -(q/p) if p = q = 3 (mod 4) We come now to the three cases in question s = -1 ------ In this case, (s/p) and (s/q) depend on the congruence classes of p and q (mod 4). But, as p = q (mod 4a), p = q (mod 4), and these classes are the same. s = 2 ----- Note that, in this case, as p = q (mod 4s), we have p = q (mod 8). As (2/p) and (2/q) depend on the congruence classes of p and q (mod 8), we also have (2/p) = (2/q). s is an odd prime ----------------- Note first that p = q (mod s), so (p/s) = (q/s). We also know that p = q (mod 4). Let s', p' and q' be the congruence classes of s, p, q mod 4. We have p' = q'. If s' = 1 or p' = q' = 1, then (s/p) = (p/s) (s/q) = (q/s) and (s/p) = (s/q) If s' = p' = q' = 3, then (s/p) = -(p/s) (s/q) = -(q/s) and again (s/p) = (s/q). We can conclude that, in all cases, (s/p) = (s/q). If we run s through all the prime factors of a (and -1 if a < 0), and multiply the equations together, we get (a/p) = (a/q). - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/