Quadratic ResiduesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/