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 . In particular, where did it come from? The book also mentions . 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 , they are only the primes generated by for . 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 , it is quite easy to see that divides , which seems to me to be the heart of the proof in H&W.

While H&W give the factorization of and , 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 is of the form . According to these pages, this result, due to Euler, was improved by Lucas who noted that in fact will be even, so the power of 2 is really . 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 . Since a factor must be of the form , you can start picking values for to find factors. Chris brought up the idea of asking how large a you would have to consider. We decided that since , you need to consider up to about . Actually, we were getting 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 occurs before you try too many values for .

Chris brought up something I had thought about as well just before the meeting, concerning the relation . This looks rather like the formula which, when denotes the -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 and an integer , consider the sequence . Besides , are there other values for 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 for various . In H&W they prove that there infinitely many primes of the form and . 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 . 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 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 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 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 be prime came in. Of course, I have no idea where the involution 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: dirichlet, euler, fermat, hardy and wright, number theory, prime

March 28, 2009 at 2:48 pm |

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

April 20, 2009 at 1:27 am |

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