Senior Projects 3: Eisenstein
Jun. 11th, 2006 09:17 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowStudent #3 was another of those who took my Development of Modern Mathematics course this spring. I've had him in a number of classes, and he's pretty consistently been on top. He expressed an interest in algebra, so I decided to give him something challenging: the Quadratic Reciprocity Theorem.
I've mentioned this theorem before, as being one of the most beautiful in all of mathematics. It was conjectured by Leonhard Euler, but it was Karl Friedrich Gauss who first proved it. (Why, I wonder, does it seem OK to give his last name or all three, but "Karl Gauss" seems incomplete?) In fact, Gauss was so taken with the theorem that he came up with a number of different proofs of it. (And why not? Michelangelo sculpted four different Pietas, and each says something different about the subject; likewise Gauss's multiple proofs.) The proof most commonly given in number theory texts was discovered somewhat later by Ferdinand Eisenstein, who also devised analogous Cubic and Biquadratic Reciprocity theorems. (They're not as pretty as the QRT, for technical reasons, but they did point the way toward later, even broader extensions.) This student's task is to master and present Eisenstein's proof.
Suppose p and q are two odd prime numbers. There are two questions you can ask: Is there a perfect square that differs from q by a multiple of p? Is there a perfect square that differs from p by a multiple of q? For example, if p and q are 5 and 11 respectively, the answer to both questions is "Yes". (16=42 works, both times.) If they're 5 and 7, both answers are "No". (I'll discuss why in the blockquotes.) If they're 3 and 7, the first answer is "Yes", but the second is "No". The remarkable thing is this: both questions have the same answer, unless p and q are both one less than a multiple of 4, in which case they have opposite answers. That's the Quadratic Reciprocity Theorem: "quadratic", because it deals with perfect squares, and "reciprocity", because of the reciprocal relationship between the two questions. The Cubic Reciprocity Theorem compares the answers to the same questions, but with cubes rather than squares; Biquadratic Reciprocity deals with fourth powers; and there's a very broad theorem, called Artin Reciprocity, which (once you unpack it) includes the three earlier theorems as special cases, and more besides. (The mathematician who discovered the general theorem was Michael Artin, whence the name.)
I've mentioned this theorem before, as being one of the most beautiful in all of mathematics. It was conjectured by Leonhard Euler, but it was Karl Friedrich Gauss who first proved it. (Why, I wonder, does it seem OK to give his last name or all three, but "Karl Gauss" seems incomplete?) In fact, Gauss was so taken with the theorem that he came up with a number of different proofs of it. (And why not? Michelangelo sculpted four different Pietas, and each says something different about the subject; likewise Gauss's multiple proofs.) The proof most commonly given in number theory texts was discovered somewhat later by Ferdinand Eisenstein, who also devised analogous Cubic and Biquadratic Reciprocity theorems. (They're not as pretty as the QRT, for technical reasons, but they did point the way toward later, even broader extensions.) This student's task is to master and present Eisenstein's proof.
Suppose p and q are two odd prime numbers. There are two questions you can ask: Is there a perfect square that differs from q by a multiple of p? Is there a perfect square that differs from p by a multiple of q? For example, if p and q are 5 and 11 respectively, the answer to both questions is "Yes". (16=42 works, both times.) If they're 5 and 7, both answers are "No". (I'll discuss why in the blockquotes.) If they're 3 and 7, the first answer is "Yes", but the second is "No". The remarkable thing is this: both questions have the same answer, unless p and q are both one less than a multiple of 4, in which case they have opposite answers. That's the Quadratic Reciprocity Theorem: "quadratic", because it deals with perfect squares, and "reciprocity", because of the reciprocal relationship between the two questions. The Cubic Reciprocity Theorem compares the answers to the same questions, but with cubes rather than squares; Biquadratic Reciprocity deals with fourth powers; and there's a very broad theorem, called Artin Reciprocity, which (once you unpack it) includes the three earlier theorems as special cases, and more besides. (The mathematician who discovered the general theorem was Michael Artin, whence the name.)
If p is any odd prime and n is any number not divisible by p, we call n a "quadratic residue" mod p if there's a perfect square which differs from n by a multiple of p; in modern notation, there is some k such that n=k2(mod p). Otherwise, n is a "quadratic nonresidue". If you think a moment, you'll see that all that matters is the remainder n leaves when you divide by p. Let's look, for a moment, at the quadratic residues and nonresidues mod 5. Every number which isn't a multiple of 5 has one of the four forms 5m+1, 5m+2, 5m+3, 5m+4. Squaring these, you get 25m2+10m+1, 25m2+20m+4, 25m2+30m+9, 25m2+40m+16, which have remainders 1, 4, 4, and 1 respectively. Therefore the quadratic residues mod 5 are those which leave a remainder of 1 or 4, and the nonresidues are those which leave a remainder of 2 or 3. Similar calculations show that the quadratic residues mod 7 correspond to the remainders 1, 2, and 4, and the nonresidues to 3, 5, and 6.
As an aid to computing these things, we use the "Legendre symbol" (n/p). (n/p) is defined to be 1 if n is a quadratic residue mod p, and -1 otherwise. The Legendre symbol has a number of interesting properties. Notably, (mn/p)=(m/p)(n/p), and (2/p)=1 if p is one more or one less than a multiple of 8, and -1 otherwise. Combining this with QRT, it becomes easy to determine whether p is a quadratic residue mod q, even if p and q are quite large. Here's an example: is 197 a quadratic residue mod 257? Well, 197 is one more (not one less) than a multiple of 4, so the first case applies: (197/257) = (257/197). But now we can take remainders: (257/197) = (60/197). 60 factors as 4*3*5, so (60/197) = (4/197) (3/197) (5/197). (4/197) is 1, since 4 is a square. Again, (3/197) = (197/3) and (5/197) = (197/5), by QRT. Take remainders: (197/3) = (2/3), which is -1, and (197/5) = (2/5), which is also -1; plugging these back in, we have that (60/197) = 1, and so 197 is a quadratic residue mod 257. What square it is that differs from 197 by a multiple of 257, I couldn't tell you without some lengthy computations, but there is one; and the fact that I can so quickly answer that is part of the beauty of the QRT.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2006-06-12 04:31 pm (UTC)For the same reason Piet Hein is always referred to by his full name. That which is the king of all.