Quadratic Residues

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