Hardy and Wright, Chapter 6

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-p congruence results as possible as results about the cyclic group of units in the integers mod p. He’s an algebraist, so it’s reasonable.

Eric told us about a relation between some of these mod-p results concerning binomial coefficients and topology. He mentioned something about the sphere spectrum, it’s localization at p, and the Eilenberg-Maclane spectrum H\mathbb{Z}. 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 a^{\frac{1}{2}(p-1)} (whose equivalence class mod p was a hot topic in this chapter) as (\sqrt{a})^{p-1}. When a is a quadratic residue, this just about makes sense (of course, it would have two roots, but both, when raised to the p-1 power, give 1 as a result). Alternatively, when a is not a quadratic residue, a^{\frac{1}{2}(p-1)}\equiv -1\pmod{p}. So when a is not a quadratic residue, I’m still tempted to think of \sqrt{a} in some relation to the imaginary number i. 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 a, find an x so that x^2\equiv a\pmod{p}). While I’m dropping names, I also noted that the result that the Fermat number F_k is prime iff F_k|(3^{\frac{1}{2}(F_k-1)}+1), 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 n is there an 0<m<n and 0<x,0\leq y so that 1+x^2+y^2=mn? It’s easy to show that this is never satisfied if n 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 n as one more than a square, or a sum of squares, for varying n. 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 2^{p-1}-1\equiv 0\pmod{p^2}, 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 h, 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 p divides the Fermat number F_n=2^{2^n}+1, then there is a k so that p=k2^{n+2}+1.

Proof: Since 2^{2^n}\equiv -1\pmod{p} by assumption, we see easily that (2^{2^n})^2=2^{2^{n+1}}\equiv 1\pmod{p}, and so by Fermat’s theorem, 2^{n+1}|p-1, which is to say p=k'\cdot 2^{n+1}+1 (this is Euler’s result). It remains to be seen that k' is even. If n\geq 2 then p=k'\cdot 2^{n+1}+1\equiv 1\pmod{8}, meaning p is of the form 8t+1. Since we studied the quadratic character of 2, we know that 2 is a quadratic residue of a prime of this form, and so 2^{\frac{1}{2}(p-1)}\equiv 1\pmod{p}. Thus, \frac{1}{2}(p-1) is divisible by 2^{n+1}, and so p-1 is divisible by 2^{n+2}, which was our goal. Of course, one should check the claim for the numbers F_0 and F_1.

Since the product of two numbers of the form k2^{n+2}+1 has the same form, the theorem can actually be stated about any divisor of Fermat numbers, not just prime divisors.


Tags: , , , , ,

3 Responses to “Hardy and Wright, Chapter 6”

  1. Anonymous Says:

    None of us in the meeting seemed to know if there was some reasonable connection here, so perhaps a reader can fill us in?

    Look at the field F_p(sqrt(a)), which equals F_p when a is a quadratic result and otherwise is a quadratic extension. In that field, a^((p-1)/2) is indeed the (p-1)-st power of sqrt(a). Of course, Fermat’s little theorem fails in the extension field, so you don’t just get 1. Instead, the Frobenius automorphism x -> x^p is the same as conjugation (it’s the unique automorphism of F_p(sqrt(a)) besides the identity). Conjugating twice gives the identity, so everything splits up into +1 and -1 eigenspaces. The +1 eigenspace is F_p itself and the -1 eigenspace is the F_p multiples of sqrt(a). Now x^(p-1) = x^p/x, so for x=sqrt(a) you get -1. This isn’t the simplest explanation. (That would probably come from factoring x^(p-1)-1 = (x^((p-1)/2)+1)(x^((p-1)/2)-1) and observing that the quadratic residues use up all the roots of the second factor.) However, you are right that thinking about the (p-1)-st power of sqrt(a) puts this in a better context and lets you apply a lot of tools.

  2. sumidiot Says:

    Thanks, @Anonymous! I’ve forgotten most of the algebra I’ve learned, but recognize most of the things you mention. So, for me, yours is a pretty dense paragraph, but it’ll certainly be worth taking the time for me to unravel.

  3. Qiaochu Yuan Says:

    Re: higher residues and the quadratic character of 2:

    1) Gauss didn’t stop his work at quadratic residues: he investigated cubic and quartic residues, as did many afterwards (and some before). What ends up happening is that these higher-order reciprocity laws are best stated, not in the integers, but in extensions thereof: for example, quartic reciprocity looks prettiest in the Gaussian integers, and cubic reciprocity looks prettiest in the Eisenstein integers. Further generalizations are quite deep; the Wikipedia articles are a good place to start.

    2) The quadratic character of 2 is one of the two “supplementary” cases of quadratic reciprocity; the other is the quadratic character of -1. This is related to a variety of other situations in which 2 has its own special case, one reason for this basically being that the group of units mod 2 is trivial; there isn’t enough “room” for the normal behavior to happen. (This is sometimes summarized by the slogan “2 is the oddest prime!”)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: