Числа Ферма

Pierre de Fermat was a magistrate in Toulouse who did mathematics in letters rather than in books. In correspondence around 1640 with Bernard Frénicle de Bessy, Marin Mersenne and Blaise Pascal he claimed that every number of the form 2^(2^n) + 1 is prime, and was unusually candid about not being able to prove it — he told Pascal he was convinced of the result but could not establish it. The first five values, 3, 5, 17, 257 and 65537, are indeed prime, which is an uncomfortably persuasive amount of evidence.

Leonhard Euler ended it in 1732, aged twenty-five, by publishing that 4,294,967,297 = 641 × 6,700,417. He did not stumble on 641: he had proved that any factor of F(n) must have a restricted form, which cut the candidates for F(5) to a short list he could test by hand. François Édouard Anatole Lucas sharpened that constraint in 1878, and Théophile Pépin gave a clean primality criterion for Fermat numbers in 1877.

The sequence nonetheless produced one of the great results in classical geometry. On 30 March 1796, at nineteen, Carl Friedrich Gauss found that a regular 17-gon can be constructed with compass and straightedge — the first advance on the Greek constructions in two thousand years, and by his own account the thing that decided him on mathematics over philology. In the Disquisitiones Arithmeticae of 1801 he tied constructibility to the Fermat primes; Pierre Wantzel proved the converse in 1837.

Progress since has been a factoring story. Fortuné Landry split F(6) in 1880 at the age of eighty-two, a factorisation Thomas Clausen appears to have found privately in 1854 without publishing. Michael Morrison and John Brillhart cracked F(7) in 1970 with the continued fraction method, and Richard Brent and John Pollard took F(8) in 1980. Not one new Fermat prime has turned up in nearly three centuries.

Ключевые свойства

• F(n) = 2^(2^n) + 1, giving 3, 5, 17, 257, 65537, 4294967297, …
• Only F(0) through F(4) are known to be prime, and every F(n) from n = 5 to n = 32 has been proved composite.
• F(5) = 4,294,967,297 = 641 × 6,700,417, the factorisation Euler published in 1732.
• F(n) = F(0)·F(1)·…·F(n-1) + 2 for every n ≥ 1, and also F(n) = (F(n-1) - 1)² + 1.
• Any two distinct Fermat numbers are coprime, which gives Goldbach his proof that there are infinitely many primes.
• Every prime factor of F(n) for n ≥ 2 has the form k·2^(n+2) + 1 — Euler used the weaker version of this to find 641.
• Pépin's test: for n ≥ 1, F(n) is prime if and only if 3^((F(n)-1)/2) ≡ -1 (mod F(n)).
• A regular polygon with N sides is constructible with compass and straightedge exactly when N is a power of two times a product of distinct Fermat primes, so 17 and 257 sides are constructible and 7 and 9 are not.
• F(n) has floor(2^n · log10 2) + 1 decimal digits: F(5) has 10 and F(12) has 1,234.

Где встречаются

• 65537 is the near-universal RSA public exponent in TLS certificates: it is prime, and in binary it is 1 followed by fifteen zeros and a 1, so exponentiation by it costs only sixteen squarings and one multiply.
• The IDEA block cipher, published by Xuejia Lai and James Massey in 1991, multiplies modulo 65537.
• Gauss's 17-gon result is the reason Fermat primes appear in any treatment of straightedge-and-compass construction; a 17-pointed star stands on his memorial in Braunschweig, the story being that a stonemason refused the 17-gon itself because it would be indistinguishable from a circle.
• Number-theoretic transforms taken modulo a Fermat number — the "Fermat number transform" — are used for exact integer convolution in signal processing, where floating-point FFTs would introduce rounding error.
• The Cunningham Project, which tabulates factorisations of b^n ± 1, tracks the Fermat numbers as one of its headline families, and they remain standard benchmarks for new factoring algorithms.