Residues and Non-Residues

Date: 05/04/2003 at 15:27:05
From: Matt
Subject: Number theory

If p > 3, show that p divides the sum of its quadratic residue. 

I was able to show it with small primes like 13 and 17, but couldn't 
do it with general p. Any suggestions?

Date: 05/05/2003 at 06:14:50
From: Doctor Jacques
Subject: Re: Number theory

Hi Matt,

Let R be the sum of the (non-zero) quadratic residues, and N the sum 
of the non-residues.

We have:

  N + R = 0 (mod p)

(Do you see why?)

For an odd prime p, there are (p-1)/2 residues and (p-1)/2 non-
residues. If p > 3, p >= 5, and there are at least two non-residues. 
We can thus always pick a non-residue n <> p-1.

If we multiply a non-residue by a non-zero residue, the product is a 
non-residue. This means that the set:

  {nr | r <> 0 is a residue}

is exactly the set of the non-residues, since the two sets have the 
same number of elements.

We can therefore write:

  nR = N

with n <> -1 (mod p)

Can you continue from here? Please feel free to write again if you 
require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/