Associated Topics || Dr. Math Home || Search Dr. Math

### Proof Involving Legendre Symbol

```Date: 02/03/2003 at 10:01:11
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)

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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search