Quadratic ResiduesDate: 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 |
Ask Dr. MathTM
© 1994-2002 The Math Forum
http://mathforum.org/dr.math/