Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Quadratic Residues


Date: 06/30/98 at 15:42:49
From: Bill Petry
Subject: Quadratis Residues

I scanned your site for information on quadratic residues, but it 
seems I need a more fundamental explanation of the concept. 

Can you help?


Date: 06/30/98 at 15:49:44
From: Doctor Rob
Subject: Re: Quadratis Residues

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 
residues, and (p-1)/2 quadratic nonresidues.

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

[Privacy Policy] [Terms of Use]

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

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/