# Fermat numbers and the infinitude of primes

Wonder whether any of you guys know why it is that the proof of the infinitude of primes that is based on the coprimality of any pair of (distinct) Fermat numbers is commonly attributed to Pólya.

In the first paragraph of this letter from Golbach to Euler, there already appears the approach along those lines but since documents crediting it to Pólya altogether are not rare out there, it seems like it's passed unnoticed by a nonzero number of persons.

So, what do you think about this? It's not like Fermat numbers are essential to the proof or that there are no other demonstrations of the result... It's just that I'd really like to know about the origins of this discrepancy between the sources.

UPDATE: Robert Haas implies in 1 that it was Adolf Hurwitz the first mathematician that stated explicitly the fact that the coprimality of any two (distinct) Fermat numbers implies the infinitude of the prime numbers. According to Mr. Haas, Adolf Hurwitz began, in the summer of 1891, a compilation of number-theoretic problems which he would eventually entitle "Übungen zur Zahlentheorie" (follow the link if you wish to download a PDF copy of it): the coprimality of any pair of (distinct) Fermat numbers and its relation to the infinitude of the primes is the subject matter of the second entry of this compilation.

In Mr. Haas's paper one can even find a potential explanation as to why it is that the proof of the infinitude of the primes via the coprimality of any two (distinct) Fermat numbers is usually attributed to Pólya (or Pólya & Szegö, while we are at it):

"Through most of the twentieth century, until Hurwitz's book [Die Übungen zur Zahlentheorie] was printed in 1993, the primes proof was attributed to Pólya and Szegö, who presented it (without references or claim of originality) as a problem and solution in their famous 1925 'Aufgaben und Lehrsätze aus der Analysis'. But considering that Pólya was Hurwitz's colleague and posthumous editor, the idea may well have come directly from Hurwitz's 'Übungen zur Zahlentheorie'. At any rate, Hurwitz had at least 7 year's priority [the last entry of the 'Übungen zur Zahlentheorie' was added sometime in 1918]."

Nevertheless, in the light of Mr. Lemmermeyer's answer below, I consider that the real priority dispute in this matter is not between Hurwitz and Pólya (or Pólya & Szegö) but between Hermann Scheffler and Adolf Hurwitz. Oddly enough, Scheffler's "Beiträge zur Zahlentheorie, insbesondere zur Kreis und Kugeltheilung, mit einem Nachtrage zur Theorie der Gleichungen" was published in the same year in which Hurwitz began putting together his "Übungen zur Zahlentheorie"!

Do you think that it is possible to determine at this stage of the game whether Scheffler's book had something to do with Hurwitz's impulse to recognize in print what Goldbach apparently never did, i.e., that the pairwise relatively prime sequence of Fermat numbers guarantees the infinitude of the prime numbers? What is more: did Hurwitz have in his possession a copy of Scheffler's book once?

Let me close this update by quoting the paragraph of Mr. Haas's paper wherein he tells us why it is that Goldbach has never received full credit for this approach to the infinitude of the prime numbers:

"Goldbach, having showed that the Fermat numbers are pairwise relatively prime, clearly had a proof of the infinitude of primes in his hands. But being absorbed in whether the Fermat numbers are absolutely prime, he overlooked that consequence of his work. Holding a mathematical proof to be a DELIBERATE act of reasoned argument, one must therefore award shared credit to his "collaborator" 160 years later who did notice it, Hurwitz. Goldbach dug out the ore, and Hurwitz spotted the diamond and showed it off."

References

[1] R. Haas, Goldbach, Hurwitz, and the Infinitude of Primes: Weaving a Proof across the Centuries. Math Intelligencer, Vol. 36, 1, 2014.

-
Goldbach observes that Fermat numbers are coprime. Nowhere does he mention that this implies the infinitude of primes. – Franz Lemmermeyer Apr 23 '10 at 8:28
Goldbach and Euler were interested in the question whether or not all Fermat numbers are prime. Later Euler would find the factor 641 of the fifth Fermat number. An English translation of the correspondence will appear next year as part of Euler's Opera Omnia. – Franz Lemmermeyer Apr 23 '10 at 9:12
Don't know much about history, but I would have thought Euclid would know about Fermat numbers, seeing as the recursive definition $$a_1=3,\ a_{n+1}=a_1a_2\cdots a_n+2$$ seems especially natural if you consider $3$ to be the smallest prime number, as I've been told Euclid did. – bof Apr 22 '15 at 20:47

It's interesting that the coprimality of Fermat numbers was already known in Goldbach's time. The reason for attributing the proof to Polya is presumably that such a proof is indicated as an exercise in Polya and Szego (1924). Because of this, Ribenboim, in his Little Book of Big Primes calls it "Polya's proof." Maybe the rumor started there.

[Added later] In the light of the comments that have come in, it now looks to me as though 1. Goldbach could have observed that he had a proof of the infinitude of primes, but didn't care to mention it, and 2. that the attribution of this observation to Polya starts with Hardy.

Re 1. In the 18th century, were people interested in finding new proofs of the infinitude of primes? For example, when Euler proved that $\Sigma 1/p=\infty$ (paper E72 in the Euler Archive) he did not remark that this gives a new proof of the infinitude of primes. It could very well be that Goldbach did not consider it interesting to prove again that there are infinitely many primes.

Re 2. One should bear in mind that Hardy knew Polya well. Polya visited him in England just after the publication of Polya & Szego and collaborated with him on the book Inequalities, published in 1934 ( four years before H&W). So Hardy could well have learned the proof directly from Polya.

-
In the Little Book of Bigger Primes he ends up ascribing it to Goldbach, though. He even adds that it was Władysław Narkiewicz the one who, after calling his attention to the afore-mentioned epistle from Goldbach to Euler, made him changed his mind on this matter. So, it seems like we're back to where we started... – José Hdz. Stgo. Apr 23 '10 at 18:13
The Polya-Szego reference is Problems and Theorems in Analysis, Volume II, Part VIII, No. 94, page 130. – Gerry Myerson May 7 '10 at 6:43
In my experience one should always be suspect of historical remarks that are not made in purely historical studies. E.g. recently I saw reference to another historical claim in Ribenboim's books - namely that Kummer was the source of the trivial N-1 (vs. N+1) variant of Euclid's proof. I couldn't beieve that Kummer would make such a trivial remark. In fact he didn't. Rather, he had in mind a more interesting proof based on the phi-function. Since this emargin is too small for the proof, please see [2] for the details. – Bill Dubuque Jul 2 '10 at 21:23
Here are said links: [1] at.yorku.ca/cgi-bin/… [2] books.google.com/… – Bill Dubuque Jul 2 '10 at 21:23

Hello,

As far as I know, the problem began with Hardy and Wright's "An introduction to the theory of numbers", first published in 1938. Indeed, in Section 2.4, page 14, they write

Second proof of Euclid’s theorem. Our second proof of Theorem 4, which is due to Polya, depends upon a property of what are called ‘Fermat’s numbers’...

Since Hardy and Wright's book has always been so popular, I suspect that many have given credit to Pólya, following their words.

Notice, however, that Dickson's 1952 "History of the theory of numbers" correctly attributed the theorem back to Goldbach (see p. 375 of Volume I):

Chr. Goldbach called Euler's attention to Fermat's conjecture that $F_n$ is always prime, and remarked that no $F_n$ has a factor $<100$; no two $F_n$ have a common factor.

-
To be 100% honest, I have not been able to spot that (second) sentence in bold in any of the epistles that Professor Dickson mentions in the corresponding footnote of his text. Also, it is really curious that Hardy and Wright adscribe the proof to Pólya. Quite the more so, when one notices that the argument showcased by them is nowhere to be found in the famous problem compendium by Pólya and Szegö. – José Hdz. Stgo. May 7 '10 at 23:41
My latin is definitely rusty, but I believe that the fact that no two F_n have a common factor is proved at the very beginning of the letter from Goldbach to Euler of July 1730 (that you linked in your original post above), and in fact, the proof alluded by Goldbach is precisely that one given by Hardy and Wright. Namely, he shows that F_n divides F_{n+p}-2, and if a number divided both, it would be 2, but F_n is odd. And then Goldbach says "...omnes numeros seriei Fermatianae esse inter se primos" (all Fermat numbers are pairwise coprime). – Álvaro Lozano-Robledo May 8 '10 at 1:45

On p. 167 of Beiträge zur Zahlentheorie, insbesondere zur Kreis- und Kugeltheilung, mit einem Nachtrage zur Theorie der Gleichungen (1891), Scheffler deduces the infinitude of primes from the fact that Fermat numbers are pairwise coprime. I don't think that Scheffler's book was widely read, however.

-
What an interesting finding, Professor Lemmermeyer! – José Hdz. Stgo. Jan 25 '12 at 0:12

I am quoting from the nice book "The development of Prime Number Theory" by W. Narkiewicz, Springer (2000), pg. 8.

Any infinite sequence of pairwise coprime positive integers leads to a proof of [the infinitude of primes]. Such a proof first appears in a letter of C.Goldbach to Euler dated July 20, 1730 [footnote: The original date is July 20/31, the double dating being a consequence of the use of the Julianic calendar in Russia before 1918. It seems that this was the first proof of the infinitude of primes which essentially differed from that of Euclid.] (see Fuss 1843, I, 32-34; Euler-Goldbach 1965) and is sometimes attributed to G.Pólya (e.g. in Hardy, Wright (1960), Chandrasekharan (1968). P.Ribenboim (Nombres premiers: mystères et records. 1994) wrote that this attribution appears in an unpublished list of exercises of A.Hurwitz preserved in ETH in Zürich.) This proof was published in the well-known collection of exercises of G.Pólya and G.Szegö (1925).

What is interesting here is that Hurwitz died in 1919, prior to Hardy & Wright, and to Pólya & Szegő, so it is likely that Pólya rediscovered the argument on his own, unaware of Goldbach's letter, presented it to colleagues, and they would naturally attribute it to him.

-
Thanks for taking the time to post that paragraph, Señor Caicedo. I think it is a great complement to the remarks made by J. Stillwell in his answer. – José Hdz. Stgo. May 29 '10 at 9:44
BREAKING NEWS: A. Hurwitz's list of exercises in Number Theory was actually published in 1993! A PDF copy of the transcription of this document can be found here: goo.gl/vVGJPW Guess what... In the part where Hurwitz writes about the coprimality of any two distinct Fermat numbers, there appears no attribution whatsoever to G. Pólya. Hence, it seems that Prof. Narkiewicz is off the mark in at least two respects in that paragraph of his "The development of Prime Number Theory". – José Hdz. Stgo. Apr 10 '15 at 7:57

@Álvaro:

1. Agreed that a proof of the coprimality of any pair of distinct Fermat numbers appears in the very first paragraph of the aforementioned missive from Goldbach to Euler. That is not under discussion here. Thing is that, as Professor Lemmermeyer noted above, Goldbach himself did not seem to notice that this result would (immediately) provide him with a proof of the infinitude of the primes. As I commented before, one of my initials beliefs on this matter was that the exclamation "at quantulum hoc est ad demonstrandum omnes illos numeros esse absolute primos?" in the July 20th letter was somehow implying that Golbach had actually found the connection between both facts. Yet, your knowledgeable comments have just made me change my mind on this wrong impression that I initially had.

2. You are absolutely right when you express that the proof given by Hardy and Wright passes through the argument given by Goldbach in his letter to Euler. That's the reason that I said it is kind of weird to see H & W adscribing the result to Pólya.

-
Even though Goldbach does not mention that this implies the infinitude of the primes, it is such an immediate consequence that I think we all agree that the credit should go to Goldbach. By my comment above I only meant to point out that Goldbach did say "no two F_n have a common factor" (in the "...inter se primos" comment), as Dickson mentions. By the way, the sentence "at quantulum..." means "but how close is this to a proof that all Fermat numbers are primes?", so he is referring to Fermat's conjecture that all F_n are primes, and not to the fact that there are infinitely many primes. – Álvaro Lozano-Robledo May 8 '10 at 13:34
"... inter se primos" Of course! How could I forget about it? As to whether we all agree that the credit should go to Golbach, I'm not that sure. Nonetheless, I think that we all definitely agree that people ought not to continue adscribing it exclusively to Professor Pólya. – José Hdz. Stgo. May 8 '10 at 15:21
Interestingly, in Spanish sometimes we say "primos entre sí", which means coprime, but now I realize the direct latin origin of this phrase (inter se primos). – Álvaro Lozano-Robledo May 9 '10 at 0:44