fermat | ∑idiot's Blog

Posts Tagged ‘fermat’

Hardy and Wright, Chapter 6

April 20, 2009

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:dedekind, euler, fermat, gauss, hardy and wright, number theory
Posted in Play | 3 Comments »

Hardy and Wright, Chapter 2

March 20, 2009

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.