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

### 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/
```
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