The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.