Quadratic ResiduesDate: 03/19/2004 at 01:02:09 From: Jeanne Subject: quadratic residues I don't fully understand the concept of quadratic residues. Here's what I do understand. Given x^2==a(mod p), 'a' is a quadratic residue if there exists a solution to the congruence. If 'a' does not give a solution, a is a non-residue. Furthermore, given the theorem: Let p be an odd prime. There are exactly (p - 1)/2 incongruent quadratic residues of p and exactly (p - 1)/2 quadratic nonresidues of p. Can you provide an example that helps explain this concept? My book doesn't give any examples. Date: 03/19/2004 at 02:57:18 From: Doctor Jacques Subject: Re: quadratic residues Hi Jeanne, The quadratic residues modulo n are simply the squares modulo n. (Note: this is a concept of modular arithmetic, so I'll not write "mod n" or "mod p" after each line--consider this as implicit). For example, for n = 15 (n need not be a prime), the elements of Z_15 (the residue classes modulo 15) are 0, 1, ... 14. If we look at the squares of these elements, we get the table: x | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ----+--------------------------------------------- x^2 | 0 1 4 9 1 10 6 4 4 6 10 1 9 4 1 (For example, in the 6th column, we have 5^2 = 25 = 10 (mod 15)). The elements in the second row are the squares modulo 15: {0, 1, 4, 6, 9, and 10}; these numbers are called quadratic residues (mod 15), because, if q is one of these numbers, the equation: x^2 = q (mod 15) has at least one solution (to find solutions, look for q in the second row; the solutions are the corresponding numbers in the first row). For example, q = 4 is a quadratic residue, since 4 appears in the second row of the table. The solutions of the equation x^4 = 4 are the numbers in the first row above the 4's in the second row, in this case 2, 7, 8, and 13 (note that this second-degree equation has more than 2 solutions--this is because 15 is not prime). On the other hand, 7 is not a quadratic residue modulo 15, since it does not appear in the second row of the table; there is no number x such that x^2 = 7 (mod 15). Modulo 10, the quadratic residues are {0, 1, 4, 5, 6, 9}. These are the only possible unit digits for a perfect square. As (-x)^2 = x^2, the table has left-to-right symmetry; the residues in the right half are the same as those in the left half. This already shows that there cannot be more than n/2 residues. If n = p is prime, however, we can say more. Let us look at a specific example, p = 7: x | 0 1 2 3 4 5 6 -----+--------------------- x^2 | 0 1 4 2 2 4 1 We see that the residues are 0, 1, 2, and 4 (0 is sometimes excluded from the list as a special case). If p is prime, the equation: x^2 = a (mod p) cannot have more than 2 solutions. Indeed, if x0 is one solution, we have: x^2 = x0^2 (mod p) (x^2 - x0^2) = 0 (mod p) (x - x0)(x + x0) = 0 (mod p) The last line shows that p divides the product (x - x0)(x + x0). *As p is prime*, it must divide one of the factors, i.e., we must have either p | (x - x0) - which means x = x0, or p | (x + x0), which means x = -x0. This shows that we can have at most two solutions, x0 and -x0. If p > 2 and x is not 0, x0 and -x0 are different (mod p). In that case, either we have no solution at all (a is a non-residue), or we have exactly two solutions (a is a residue). Note also that x^2 = 0 (mod p) has exactly one solution x = 0 (this would not be the case if p were not prime, for example, x^2 = 0 has 3 solutions modulo 9: 0, 3, 6). To summarize, if we exclude 0, there are p - 1 columns in the table. In the second row, each entry is a number between 1 and p - 1, and appears twice (in symmetrical positions). This means that half of the available numbers [(p - 1)/2] do appear as quadratic residues, and the other half do not appear in the second row and are non-residues. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 03/21/2004 at 19:07:27 From: Jeanne Subject: quadratic residues This really helped me! After days of reading my book and trying to figure it out, it finally makes sense to me. Thank you so very, very much!!! I am going to continue in my book with the Law of Quadratic Reciprocity, which I'm hoping now will make sense to me. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/