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

```
Date: 06/30/98 at 15:42:49
From: Bill Petry

seems I need a more fundamental explanation of the concept.

Can you help?
```

```
Date: 06/30/98 at 15:49:44
From: Doctor Rob

You should be familiar with modular arithmetic for this explanation.
A quadratic residue modulo p is a number r with 0 <= r < p, such that
there exists an x with x^2 = r (mod p). In words, r is the remainder
when you divide some square by p.

If p > 2 is a prime, it turns out that there are (p+1)/2 quadratic

Example:  p = 11

0^2 = 0 (mod 11)
1^2 = 1 (mod 11)
2^2 = 4 (mod 11)
3^2 = 9 (mod 11)
4^2 = 5 (mod 11)
5^2 = 3 (mod 11)
6^2 = 3 (mod 11)
7^2 = 5 (mod 11)
8^2 = 9 (mod 11)
9^2 = 4 (mod 11)
10^2 = 1 (mod 11)

Thus the quadratic residues modulo 11 are 0, 1, 3, 4, 5, and 9. The
other numbers between 0 and 11 are quadratic nonresidues modulo 11:
2, 6, 7, 8, and 10.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School 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