Proof Involving Legendre Symbol

Date: 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/