Last week’s exploration into “Congruences and Residues” primed us (no pun intended) for Chapter 6 of Hardy and Wright, “Fermat’s Theorem and its Consequences”. This was, for me, the most challenging chapter so far. Luckily, we had our largest attendance to date (four) to get through it.
Chris started out by telling us that he thinks about as many of these mod- congruence results as possible as results about the cyclic group of units in the integers mod . He’s an algebraist, so it’s reasonable.
Eric told us about a relation between some of these mod- results concerning binomial coefficients and topology. He mentioned something about the sphere spectrum, it’s localization at , and the Eilenberg-Maclane spectrum . Perhaps he’d help us out by providing those remarks in the comments, as I’m not particularly familiar with them.
I asked if anybody knew if there was some way I was allowed to think about (whose equivalence class mod was a hot topic in this chapter) as . When is a quadratic residue, this just about makes sense (of course, it would have two roots, but both, when raised to the power, give 1 as a result). Alternatively, when is not a quadratic residue, . So when is not a quadratic residue, I’m still tempted to think of in some relation to the imaginary number . None of us in the meeting seemed to know if there was some reasonable connection here, so perhaps a reader can fill us in?
While I’m talking about quadratic residues, I should point out that the Mathworld page on quadratic residues has some fun pictures.
I then mentioned that I had found the Shanks-Tonelli algorithm for finding the “square root” of a quadratic residue (that is, given a quadratic residue , find an so that ). While I’m dropping names, I also noted that the result that the Fermat number is prime iff , at the end of section 6.14, sometimes goes by the name of Pepin’s Test.
Next, I mentioned that I had spent some time thinking about Theorems 86 and 87 for composite moduli. The question is: For which is there an and so that ? It’s easy to show that this is never satisfied if is 4, or a multiple thereof. Eric noted that this was easy to see by thinking about the squares mod 4 (only 0 and 1 are squares mod 4). I found this to be a fun little problem to use as inspiration for learning a little more python, and generated a big table of how to write multiples of as one more than a square, or a sum of squares, for varying . Turns out, there are many ways, in general, of doing so.
I asked if anybody had any ideas what it was about 1093 that made it one of the two known primes so that , in relation to Theorem 91. That is, was there something I should have gleaned from the proof? Nobody was particularly sure, but Eric thought maybe there was some relation to regular primes (or irregular). This is a topic that’ll apparently come up later in the book, but Eric told us that it was related to some statements about Dedekind domains and the class group. When we looked up the regular and irregular primes on the Online Encyclopedia of Integer Sequences, though, Eric guessed that maybe it was something else, as there are quite a few of both type. For your convenience, the regular primes are sequence A007703, and the irregulars are A000928.
I guess this last question of mine wasn’t particularly bright. If more were known about why 1093 worked, I feel like either people would have found more, or there would be proofs that there weren’t others. Perhaps I could look into it some more. Either way, it was only the beginning of my poor questions. I also asked why it was we were studying quadratic residues, instead of, say, triadic (?) or higher. My guess, which Eric seconded, was that it was simply the next easiest thing to consider after linear residues, which are somewhat straightfoward. We both guess that things are harder to say about higher powers. I suddenly wonder about higher powers of 2 though… quartic, octic… I’m just making up words.
My remaining not particularly bright question was why there was a whole section about the “quadratic character of 2.” Why 2, in particular? We decided that it was just because it was next after 1, and the answer was relatively easy to obtain. Andy pointed out that, since the quadratic character of -3 was done in the book, as was -1, the quadratic character of 3 was known, using the result about products of quadratic residues and non-residues.
In the 6th edition of the book (the one I’m using, to which all references refer) there is a typo in theorem 97, which we verified because Andy has an older version of the text, without the typo (so… they re-typed the text? I almost think that’s a job I could handle happily. I’ve done it before [pdf]). In the theorem, they make a claim about when 7 is a quadratic residue, and then return to prove the theorem after Gauss’ law of reciprocity. However, when they return, they actually prove a theorem about 5, not 7. I tried my hand at 7, but it seemed hard to say anything about it (at least, consider primes of various classes mod 10).
Eric asked about the efficiency of the primality tests that occupy the second to last section of this chapter (Theorems 101 and 102). None of us seemed to know anything, but my guess was that finding the element , that seems to help out both of these tests, was not easy. But I really have no idea.
Finally, we concluded with my account of Carmichael’s paper “Fermat Numbers” in the American Mathematical Monthly, V. 26 No. 4 from 1919, pp 137-146 (available (in a sense) at JSTOR here). At least, my account of the part about Euler/Lucas’ result on divisors of Fermat numbers, which I mentioned in our discussion of chapter 2. For completeness or so, allow me to present the proof here.
Theorem: If the prime divides the Fermat number , then there is a so that .
Proof: Since by assumption, we see easily that , and so by Fermat’s theorem, , which is to say (this is Euler’s result). It remains to be seen that is even. If then , meaning is of the form . Since we studied the quadratic character of 2, we know that 2 is a quadratic residue of a prime of this form, and so . Thus, is divisible by , and so is divisible by , which was our goal. Of course, one should check the claim for the numbers and .
Since the product of two numbers of the form has the same form, the theorem can actually be stated about any divisor of Fermat numbers, not just prime divisors.