Hardy and Wright, Chapter 2

Not too long ago I decided it would be fun to read through Hardy and Wright’s “An Introduction to the Theory of Numbers” book (I’ll just say H&W from now on, and textual references are with respect to the 6th edition). I figured other grad students in the department might like to join me, and a few did. We’re thinking about maybe reading a chapter a week or so, with no particular goals in mind besides: “learn some stuff”. I know that I will learn quite a lot reading this book. But anyway, we had our first meeting today, and I thought I’d post some of the things we talked about. We didn’t talk, in particular, about much from chapter 1, but chapter 2 had several interesting things in it. I’ll work my way backwards through chapter 2, following how our meeting went. Our setup, as a group, is just to come in with whatever questions we had from the reading, and any outside information we looked into, inspired by the reading.

The first thing we talked about was prime generating functions. In particular, Chris mentioned that he was amused by the comment in the book about how the identity function generates all the primes. I commented that I was still in the dark about the prime generating polynomial n^2-n+41. In particular, where did it come from? The book also mentions n^2-79n+1601=(n-40)^2+(n-40)+41. I had seen that polynomial before, but only in the first form. From the second form, it’s fairly easy to see that it’s just a shift of the first quadratic, and that while it generates only primes for 0\leq n\leq 79, they are only the primes generated by n^2-n+41 for 0\leq n\leq 40. It just hits each of those primes twice, which the book doesn’t explicitly state, but I suppose is obvious enough (especially if you read it off Mathworld, which I believe I did).

We also commented on the existence of other prime generating polynomials, following what is mentioned in the Appendix. I seem to remember reading about one such polynomial with around 26 variables ([citation needed, my apologies]). The positive outputs of these polynomials are supposed to be primes, and the negative outputs composites. The challenge, wherever I was reading this, was that it was fairly difficult to see which inputs gave positive outputs. The Mathworld article on prime generating polynomials seems a good place to start finding out more.

Another big part of what we talked about was Fermat numbers. The text proves what is called Goldbach’s theorem (any two Fermat numbers are relatively prime) on the Wikipedia page on Fermat numbers, but I think the proof on the Wikipedia page is nicer. Using the relation F_n=F_0\cdots F_{n-1}+2, it is quite easy to see that F_n divides F_{n+k}-2, which seems to me to be the heart of the proof in H&W.

While H&W give the factorization of F_5 and F_6, little mention is made about where these factorizations come from. The Wikipedia page linked above and the Mathworld page both mention that any factor of F_n is of the form k\cdot 2^{n+1}+1. According to these pages, this result, due to Euler, was improved by Lucas who noted that in fact k will be even, so the power of 2 is really n+2. I asked about the proof of this (Euler’s would be fine for me) result, but none of us knew it. I suppose I should look into it some more.

I though I had remembered that this result made it very easy to find the factors of F_5=2^{2^5}+1=2^{32}+1. Since a factor must be of the form k\cdot 2^6+1, you can start picking values for k to find factors. Chris brought up the idea of asking how large a k you would have to consider. We decided that since \sqrt{F_5}\approx 2^{16}, you need to consider k up to about 2^{10}. Actually, we were getting 2^9 during our meeting, but I think we were off by one due to an error by me. I guess it’s nice, then, that the factor 641=10\cdot 2^5+1 occurs before you try too many values for k.

Chris brought up something I had thought about as well just before the meeting, concerning the relation F_n=F_0\cdots F_{n-1}+2. This looks rather like the formula p_1\cdots p_n+1 which, when p_i denotes the i-th prime, is frequently used to show there are infinitely many primes. The thought I had was something like the following. Given a starting value a_1 and an integer k, consider the sequence a_n=a_1\cdots a_{n-1}+k. Besides (a_1,k)=(3,2), are there other values for a_1,k that give known, interesting, sequences? I may practice my python this weekend and generate the starts of some sequences for small values, and see if anything noteworthy pops up.

Next we talked about primes of the form a\cdot n-1 for various a. In H&W they prove that there infinitely many primes of the form 4n-1 and 6n-1. The proofs they give rely on the fact that, mod 4 or mod 6, the only way to get a product equal to -1 is to use a -1 somewhere. I had wondered (rather naively, apparently) if this same proof extended to other values of a. However, mod 5 you can get -1 with two 2s (as Andy pointed out), and mod 7 you can get -1 with 2 and 3. My next (again, naive) thought was maybe for even a it worked, but mod 8 you can get -1 as 3 and 5. So, no luck there. What’s the general proof then? This is a case of Dirichlet’s theorem, which the book mentions (and they point out that the proof is too hard to include in this book). According to the book this is an easy case. Something more for me to look into I guess.

Finally, I brought up this wonderful proof that every prime of the form 4n+1 is the sum of two primes. Mostly I brought it up because I hadn’t been able to follow the whole thing. What’s funny about that is the original paper it was published in is titled “A One-Sentence Proof That Every Prime p\equiv 1\pmod 4 Is a Sum of Two Squares.” So I couldn’t even make my way through a one-sentence proof :). Of course, those are generally the most dense. But with a little talking things out, Chris and I got things sorted. And I finally saw where the assumption that p be prime came in. Of course, I have no idea where the involution g in that paper (or blog post) come from, but I printed out Heath-Brown’s paper “Fermat’s Two Squares Theorem” paper, found from this Wikipedia page, so perhaps I’ll gain some understanding from that. After figuring out this proof, Chris presented the proof given in an Algebra course he took a few years ago, using Gaussian integers.

All in all, a pretty good first (non-organizational) meeting.


Tags: , , , , ,

2 Responses to “Hardy and Wright, Chapter 2”

  1. Hardy and Wright, Chapter 3 « Sumidiot’s Blog Says:

    […] sumidiot Well, somewhat surprisingly, my little reading group hasn’t yet disbanded entirely. Last week we had a great discussion about chapter 2 of H&W, which put us in chapter 3 for this […]

  2. Hardy and Wright, Chapter 6 « Sumidiot’s Blog Says:

    […] 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 […]

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: