Fermat Number

A Binomial Number of the form $F_n=2^{2^n}+1$. The first few for $n=0$, 1, 2, ... are 3, 5, 17, 257, 65537, 4294967297, ... (Sloane's A000215). The number of Digits for a Fermat number is

$$D(n) = \lfloor\, [\log(2^{2^n}+1)]+1\rfloor \approx \lfloor \log(2^{2^n})+1\rfloor$$

$$= \lfloor 2^n\log 2+1\rfloor.$$ (1)

Being a Fermat number is the Necessary (but not Sufficient) form a number

$$N_n\equiv 2^n+1$$ (2)

must have in order to be Prime. This can be seen by noting that if $N_n=2^n+1$ is to be Prime, then $n$ cannot have any Odd factors $b$ or else $N_n$ would be a factorable number of the form

$$2^n+1=(2^a)^b+1 = (2^a+1)[2^{a(b-1)}-2^{a(b-2)}+2^{a(b-3)}-\ldots+1].$$ (3)

Therefore, for a Prime $N_n$, $n$ must be a Power of 2.

Fermat conjectured in 1650 that every Fermat number is Prime and Eisenstein (1844) proposed as a problem the proof that there are an infinite number of Fermat primes (Ribenboim 1996, p. 88). At present, however, only Composite Fermat numbers $F_n$ are known for $n\geq 5$. An anonymous writer proposed that numbers of the form $2^2+1$, $2^{2^2}+1$, $2^{2^{2^2}}+1$ were Prime. However, this conjecture was refuted when Selfridge (1953) showed that

$$F_{16}=2^{2^{16}}+1=2^{2^{2^{2^2}}}+1$$ (4)

is Composite (Ribenboim 1996, p. 88). Numbers of the form $a^{2^n}+b^{2^n}$ are called generalized Fermat numbers (Ribenboim 1996, pp. 359-360).

Fermat numbers satisfy the Recurrence Relation

$$F_m=F_0F_1\cdots F_{m-1}+2.$$ (5)

$F_n$ can be shown to be Prime iff it satisfies Pépin's Test

$$3^{(F_n-1)/2}\equiv -1\ \left({{\rm mod\ } {F_n}}\right).$$ (6)

Pépin's Theorem

$$3^{2^{2^n-1}}\equiv -1\ \left({{\rm mod\ } {F_n}}\right)$$ (7)

is also Necessary and Sufficient.

In 1770, Euler showed that any Factor of $F_n$ must have the form

$$2^{n+1}K+1,$$ (8)

where $K$ is a Positive Integer. In 1878, Lucas increased the exponent of 2 by one, showing that Factors of Fermat numbers must be of the form

$$2^{n+2}L+1.$$ (9)

If

$$F=p_1p_2\cdots p_r$$ (10)

is the factored part of $F_n=FC$ (where $C$ is the cofactor to be tested for primality), compute

$$A \equiv 3^{F_n-1} {\rm\ (mod\ } F_n)$$ (11)

$$B \equiv 3^{F-1} {\rm\ (mod\ } F_n)$$ (12)

$$R \equiv A-B {\rm\ (mod\ } C).$$ (13)

Then if $R\equiv 0$, the cofactor is a Probable Prime to the base $3^F$; otherwise $C$ is Composite.

In order for a Polygon to be circumscribed about a Circle (i.e., a Constructible Polygon), it must have a number of sides $N$ given by

$$N=2^kF_0\cdots F_n,$$ (14)

where the $F_n$ are distinct Fermat primes. This is equivalent to the statement that the trigonometric functions $\sin(k\pi/N)$, $\cos(k\pi/N)$, etc., can be computed in terms of finite numbers of additions, multiplications, and square root extractions iff $N$ is of the above form. The only known Fermat Primes are

$$F_0 = 3$$

$$F_1 = 5$$

$$F_2 = 17$$

$$F_3 = 257$$

$$F_4 = 65537$$

and it seems unlikely that any more exist.

Factoring Fermat numbers is extremely difficult as a result of their large size. In fact, only $F_5$ to $F_{11}$ have been complete factored, as summarized in the following table. Written out explicitly, the complete factorizations are

$$F_5 = 641\cdot 6700417$$

$$F_6 = 274177\cdot 67280421310721$$

$$F_7 = 59649589127497217\cdot 5704689200685129054721$$

$$F_8 = 1238926361552897 \cdot 93461639715357977769163\cdots$$

$$\phantom{=} \cdots 558199606896584051237541638188580280321$$

$$F_9 = 2424833\cdot 74556028256478842083373957362004\cdots$$

$$\phantom{=} \cdots 54918783366342657\cdot P99$$

$$F_{10} = 45592577\cdot 6487031809 \cdot 46597757852200185\cdots$$

$$\phantom{=} \cdots 43264560743076778192897\cdot P252$$

$$F_{11} = 319489\cdot 974849\cdot 167988556341760475137$$

$$\phantom{=} \cdot 3560841906445833920513\cdot P564.$$

Here, the final large Prime is not explicitly given since it can be computed by dividing $F_n$ by the other given factors.

$F_n$	Digits	Factors	Digits	Reference
5	10	2	3, 7	Euler 1732
6	20	2	6, 14	Landry 1880
7	39	2	7, 22	Morrison and Brillhart 1975
8	78	2	16, 62	Brent and Pollard 1981
9	155	3	7, 49, 99	Manasse and Lenstra (In Cipra 1993)
10	309	4	8, 10, 40, 252	Brent 1995
11	617	5	6, 6, 21, 22, 564	Brent 1988

Tables of known factors of Fermat numbers are given by Keller (1983), Brillhart et al. (1988), Young and Buell (1988), Riesel (1994), and Pomerance (1996). Young and Buell (1988) discovered that $F_{20}$ is Composite, and Crandall et al. (1995) that $F_{22}$ is Composite. A current list of the known factors of Fermat numbers is maintained by Keller, and reproduced in the form of a Mathematica ${}^{\scriptstyle\circledRsymbol}$ notebook by Weisstein. In these tables, since all factors are of the form $k 2^n+1$, the known factors are expressed in the concise form $(k,n)$. The number of factors for Fermat numbers $F_n$ for $n=0$, 1, 2, ... are 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 5, ....

See also Cullen Number, Pépin's Test, Pépin's Theorem, Pocklington's Theorem, Polygon, Proth's Theorem, Selfridge-Hurwitz Residue, Woodall Number

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 68-69 and 94-95, 1987.

Brent, R. P. ``Factorization of the Eighth Fermat Number.'' Amer. Math. Soc. Abstracts 1, 565, 1980.

Brent, R. P. ``Factorisation of F10.'' http://cslab.anu.edu.au/~rpb/F10.html.

Brent, R. P ``Factorization of the Tenth Fermat Number.'' Math. Comput. 68, 429-451, 1999. ftp://nimbus.anu.edu.au/pub/Brent/rpb161tr.ps.gz.

Brent, R. P. and Pollard, J. M. ``Factorization of the Eighth Fermat Number.'' Math. Comput. 36, 627-630, 1981.

Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of $b^n\pm 1$, $b=2$, $3, 5, 6, 7, 10, 11, 12$ Up to High Powers, rev. ed. Providence, RI: Amer. Math. Soc., pp. 1xxxvii and 2-3 of Update 2.2, 1988.

Cipra, B. ``Big Number Breakdown.'' Science 248, 1608, 1990.

Conway, J. H. and Guy, R. K. ``Fermat's Numbers.'' In The Book of Numbers. New York: Springer-Verlag, pp. 137-141, 1996.

Cormack, G. V. and Williams, H. C. ``Some Very Large Primes of the Form $k\cdot 2^m+1$.'' Math. Comput. 35, 1419-1421, 1980.

Courant, R. and Robbins, H. What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 25-26 and 119, 1996.

Crandall, R.; Doenias, J.; Norrie, C.; and Young, J. ``The Twenty-Second Fermat Number is Composite.'' Math. Comput. 64, 863-868, 1995.

Dickson, L. E. ``Fermat Numbers $F_n=2^{2^n}+1$.'' Ch. 15 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, pp. 375-380, 1952.

Dixon, R. Mathographics. New York: Dover, p. 53, 1991.

Euler, L. ``Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus.'' Acad. Sci. Petropol. 6, 103-107, ad annos 1732-33 (1738). In Leonhardi Euleri Opera Omnia, Ser. I, Vol. II. Leipzig: Teubner, pp. 1-5, 1915.

Gostin, G. B. ``A Factor of $F_{17}$.'' Math. Comput. 35, 975-976, 1980.

Gostin, G. B. ``New Factors of Fermat Numbers.'' Math. Comput. 64, 393-395, 1995.

Gostin, G. B. and McLaughlin, P. B. Jr. ``Six New Factors of Fermat Numbers.'' Math. Comput. 38, 645-649, 1982.

Guy, R. K. ``Mersenne Primes. Repunits. Fermat Numbers. Primes of Shape $k\cdot 2^n+2$.'' §A3 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 8-13, 1994.

Hallyburton, J. C. Jr. and Brillhart, J. ``Two New Factors of Fermat Numbers.'' Math. Comput. 29, 109-112, 1975.

Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 14-15, 1979.

Keller, W. ``Factor of Fermat Numbers and Large Primes of the Form $k\cdot 2^n+1$.'' Math. Comput. 41, 661-673, 1983.

Keller, W. ``Factors of Fermat Numbers and Large Primes of the Form $k\cdot 2^n+1$, II.'' In prep.

Keller, W. ``Prime Factors $k\cdot 2^n+1$ of Fermat Numbers $F_m$ and Complete Factoring Status.'' http://vamri.xray.ufl.edu/proths/fermat.html.

Kraitchik, M. ``Fermat Numbers.'' §3.6 in Mathematical Recreations. New York: W. W. Norton, pp. 73-75, 1942.

Landry, F. ``Note sur la décomposition du nombre $2^{64}+1$ (Extrait).'' C. R. Acad. Sci. Paris, 91, 138, 1880.

Lenstra, A. K.; Lenstra, H. W. Jr.; Manasse, M. S.; and Pollard, J. M. ``The Factorization of the Ninth Fermat Number.'' Math. Comput. 61, 319-349, 1993.

Morrison, M. A. and Brillhart, J. ``A Method of Factoring and the Factorization of $F_7$.'' Math. Comput. 29, 183-205, 1975.

Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.

Ribenboim, P. ``Fermat Numbers'' and ``Numbers $k\times 2^n\pm 1$.'' §2.6 and 5.7 in The New Book of Prime Number Records. New York: Springer-Verlag, pp. 83-90 and 355-360, 1996.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, pp. 384-388, 1994.

Robinson, R. M. ``A Report on Primes of the Form $k\cdot 2^n+1$ and on Factors of Fermat Numbers.'' Proc. Amer. Math. Soc. 9, 673-681, 1958.

Selfridge, J. L. ``Factors of Fermat Numbers.'' Math. Comput. 7, 274-275, 1953.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 13 and 78-80, 1993.

Sloane, N. J. A. Sequence A000215/M2503 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Weisstein, E. W. ``Fermat Numbers.'' Mathematica notebook Fermat.m.

Wrathall, C. P. ``New Factors of Fermat Numbers.'' Math. Comput. 18, 324-325, 1964.

Young, J. and Buell, D. A. ``The Twentieth Fermat Number is Composite.'' Math. Comput. 50, 261-263, 1988.