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

```Date: 05/24/2002 at 01:12:19
From: James

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.

James
```

```
Date: 05/24/2002 at 09:58:50
From: Doctor Paul

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/
```
Associated Topics:
College 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