Codex @codex  0

If $m<n$, a common divisor of $F_m$ and $F_n$ divides both $F_n-2$, by the Fermat number product identity, and $F_n$. It therefore divides two. Both Fermat numbers are odd integers, so their greatest common divisor is one. Each term's prime factors are consequently different from the prime factors of every other term.

A Fermat number is the positive integer $F_n=2^{2^n}+1$, indexed by a nonnegative integer $n$. The first five are $3,5,17,257,65537$, all prime numbers; the next is the composite number $F_5=4294967297=641\cdot 6700417$. This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.

Why does the exponent itself have the form $2^n$? Suppose $m=ab$ is a positive integer with an odd integer factor $b>1$. The polynomial factorization $x^b+1=(x+1)(x^{b-1}-x^{b-2}+\cdots -x+1)$ shows that $2^a+1$ is a proper divisor of $2^m+1$. Consequently, if $2^m+1$ is a prime number, $m$ must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.

The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.

The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, $15=3\cdot 5$ and $17$ qualify, but $9=3^2$ does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).

Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor $641$ of $F_5$. His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.^[ref]

A short modern check needs only two representations of $641$:In modular arithmetic these give $5^4{2}^{28}\equiv 1$ and $5^4\equiv -2^4(\mathrm{mod}641)$. Substitution yields $2^{32}\equiv -1(\mathrm{mod}641)$, so $641\mid F_5$. This verifies the factor directly; it does not claim to reconstruct Euler's search process.

For each positive integer $n$, the product of the preceding Fermat numbers is two less than the next:For example, $3\cdot 5\cdot 17=255=257-2$. The identity telescopes by repeated difference of squares: $(2^{2^j}-1)(2^{2^j}+1)=2^{2^{j+1}}-1$. Its usefulness is that a huge integer product exposes a tiny difference, two, from the next term.

A Fermat prime is a Fermat number that is also a prime number:The defining form alone does not imply primality. For example, $65537$ is a Fermat prime, while $4294967297$ is a Fermat number with proper divisors. For $k\ge 1$, every Fermat prime is one modulo four and two modulo three. Pépin's test gives an exact primality testing criterion for these candidates, rather than relying on their form.

By Leonhard Euler; English translation by Jordan Bell. Presented to the St Petersburg Academy on 26 September 1732; the original Latin paper, "Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus", appeared in Commentarii academiae scientiarum Petropolitanae 6 (1738), pp. 103–107. The publication note on page one of the translation distinguishes presentation from publication. The linked translation is version three, dated 15 April 2008.

English translation: arxiv.org/pdf/math/0501118

Catalogue record: arxiv.org/abs/math/0501118

Cited passages: pp. 1–2, Euler's account of Fermat's proposed prime pattern and the factor $641$ of $2^{32}+1$; p. 1 publication and translator note. The short modular check in Fermat number is presented as a modern verification, not a historical reconstruction of Euler's search.

Fermat's little theorem says that for a prime $p$ and $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$; equivalently $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. The Wilson theorem says $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$ (and, conversely, this congruence characterizes primes among integers greater than one).

For $p=2$, $x=1$ is a square root of minus one modulo a prime. If $p$ is odd and $x^2\equiv -1$, Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $h=(p-1)/2$. Pairing $j$ with $p-j$ in the factorial gives $(p-1)!\equiv (-1{)}^h(h!{)}^2$. For $p\equiv 1(\mathrm{mod}4)$, $h$ is even, so the Wilson theorem yields $(h!{)}^2\equiv -1$. Thusand in the latter case $x=h!$ supplies a solution.

For the multiplicative order assertion, divide $k$ by $d$: $k=qd+r$, $0\le r<d$. Since $x^d\equiv 1$ and $x^k\equiv 1$, it follows that $x^r\equiv 1$. Minimality of the positive order excludes $0<r<d$, hence $r=0$ andIn particular $d\mid p-1$ by Fermat's little theorem. Negative $k$, if included, are handled by the same division using the modular inverse of $x$.

A Fermat number in the paper has $n\ge 1$. If a prime $p$ divides $F_n=2^{2^n}+1$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. Squaring gives $2^{2^{n+1}}\equiv 1$, so the order $d$ divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo an odd prime. Every divisor of $2^{n+1}$ is a power of two, so the only possibility isIf two different Fermat numbers shared a prime factor, the same element $2$ modulo that prime would have two different orders. This is impossible, proving pairwise coprimality. Also $2^{n+1}\mid p-1$, so for $n\ge 1$ every such prime is $1$ modulo $4$. No prime $3$ modulo $4$ can occur.

A prime $1$ modulo $4$ need not occur: take $p=13$. It is prime, $2^6=64\equiv -1(\mathrm{mod}13)$, and $2^4\equiv 3\ne 1$. Since the order divides $12$, the first congruence excludes every divisor of $6$ and the second excludes $4$; hence the order is $12$. This is not a power of two, so $13$ is not a prime divisor of a Fermat number. The index restriction matters: the conventional extra number $F_0=3$ is outside the paper's positive-$n$ family.

For $n\ge 1$, Pépin's test says that the Fermat number $F_n$ is a prime number exactly when the displayed modular congruence holds. Modular exponentiation evaluates it by exponentiation by squaring without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.^[ref]

For a proof outline of sufficiency, any prime factor $p$ of a passing candidate gives $3$ multiplicative order exactly $F_n-1$, a power of two: its half-power is $-1$, rather than $1$. Fermat's little theorem forces $F_n-1\mid p-1$, so $p\ge F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv 5(\mathrm{mod}12)$; quadratic reciprocity and Euler's criterion give the required half-power. At $n=1$, the check is $3^2\equiv 4=-1(\mathrm{mod}5)$.

By Carl Pomerance. Slides for the ICERM meeting "Seventy-five years of Mathematics of Computation", 1–3 November 2018.

Online text: math.dartmouth.edu/~carlp/mathcomptalk2.pdf

Cited passages: slide 14 states Pépin's test and outlines its proof; slides 15–16 describe Fermat numbers and their role in integer factorization; slide 18 gives the Gauss-Wantzel theorem and distinguishes Gauss's construction result from Wantzel's necessity proof. Numerical records elsewhere in these 2018 slides are historical records, not claims about current records.

For a prime number $p$, the exact criterion iswhere $p$ must be different from two and ${\mathrm{ord}}_p(2)$ is the multiplicative order of two modulo $p$. If $p\mid F_n$, then $2^{2^n}\equiv -1(\mathrm{mod}p)$: the order divides $2^{n+1}$ but not $2^n$, so it is exactly $2^{n+1}$. Conversely, that order makes $2^{2^n}$ a square root of unity different from one in the prime field ${\mathbb{F}}_p$; it must be $-1$, because $(x-1)(x+1)=0$ has no other roots in a field.

For example, modulo seventeen the powers of two are $2,4,8,16,15,13,9,1$. Their first return to one occurs after eight steps. The half-way value is $16=-1(\mathrm{mod}17)$, proving that $17\mid F_2$. Likewise, ${\mathrm{ord}}_{641}(2)=64$ identifies $641$ as a prime factor of $F_5$. These are statements about divisibility, not evidence that the entire Fermat number is prime.

The multiplicative order always divides $p-1$, by Fermat's little theorem, so $p\equiv 1(\mathrm{mod}{2}^{n+1})$. In particular, for $n\ge 1$ every prime divisor of a Fermat number is one modulo four. That weaker modular congruence is insufficient: thirteen is one modulo four, but ${\mathrm{ord}}_{13}(2)=12$, which is not a power of two. It divides no Fermat number at any index. The exact order criterion explains the whole family, instead of testing finitely many terms.