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: 12 Jan 1995 11:03:51 -0500
From: , Beverly Yang
Subject: math question

        I studied number theory over the summer and we learned about quadratic 
residues (a squared modulo p, a prime).  The concept is fairly basic, but I
really don't understand the value of the concept.  Are quadratic residues used
only to prove other algorithms, or is there actually a useful application in
solving, for example, numerical problems?  Simple lemms give us some basic 
mathematical rules (i.e., 0 times a = 0, or a<b, a-b, or a>b is always true), 
but quadratic residues don't tell us much!  If you have time, PLEASE answer 
VERY  soon because this is a part of my final exam in Internet class, and I 
need an A to get an A!! Thank you so much!


Date: 12 Jan 1995 13:33:40 -0500
From: Dr. Ken
Subject: Re: math question

Hello there!

Well, I guess the verdict on the usefulness of quadratic residues kind of
depends on how useful you think number theory in general is.  Until
recently, it was kind of looked upon as the most non-useful branch of
mathematics, but it has recently found some use in cryptology and things
like that.

Anyway, the main use as I see it in quadratic residues is that you can use
them to solve quadratic congruences.  For instance, let's say you have the
congruence x^2 + 4x + 7 == 0 (mod 11).  Then you can always rewrite the
congruence in the form y^2 == a (mod 11) by completing the square like this: 
4x^2 + 16x + 28 == 0 (mod 11) 
(2x + 4)^2 == -12 (mod 11)
(2x + 4)^2 == -1 (mod 11)

So now let y=2x+4, and now we have y^2 == -1 (mod 11).  Once we've found y,
finding x will be a simple linear congruence, which is much easier than a
quadratic congruence.

But finding y could be hard.  I mean, since we're only working (mod 11) we
could just start plugging in numbers until one works (or none do), but
that's not really a good idea when your mod is big.  Quadratic congruences
can get really hard, and the standard algorithm for doing them even has a
name: RESSOL (for residue solver or something).  

So we want to see whether there's really any hope for this congruence to
have a solution, i.e. we want to see whether -1 is a quadratic residue 
(mod 11) before we start charging in there with RESSOL.

So that's one reason we study them.  The other reason I know of is that
they're just an interesting structure to look at.  Did you get a chance to
look at the quadratic reciprocity law any?  It's a nice one, and if you get
a chance, you should check it out.  Unfortunately, it's a little bit too
involved for me to get into now.  I've got a lot of questions from your
schoolmates!

-Ken "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

[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/