[go: up one dir, main page]
TOPICS
Search

Fermat Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

There are two definitions of the Fermat number. The less common is a number of the form 2^n+1 obtained by setting x=1 in a Fermat polynomial, the first few of which are 3, 5, 9, 17, 33, ... (OEIS A000051).

The much more commonly encountered Fermat numbers are a special case, given by the 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, ... (OEIS A000215). The number of digits for a Fermat number is

D(n)=|_[log(2^(2^n)+1)]+1_|
(1)
approx |_log(2^(2^n))+1_|
(2)
=1+|_2^nlog2_|.
(3)

For n=0, 1, ..., the numbers of digits in F_n are therefore 1, 1, 2, 3, 5, 10, 20, 39, 78, 155, 309, 617, 1234, ... (OEIS A057755). The numbers of digits in F_(10^n) for n=0, 1, ... are 1, 309, 381600854690147056244358827361, ... (OEIS A114484).

Being a Fermat number is the necessary (but not sufficient) form a number

N_n=2^n+1
(4)

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))-...+1].
(5)

Therefore, for a prime N_n, n must be a power of 2. No two Fermat numbers have a common divisor greater than 1 (Hardy and Wright 1979, p. 14).

Fermat conjectured in 1650 that every Fermat number is prime and Eisenstein proposed as a problem in 1844 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>=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
(6)

is composite (Ribenboim 1996, p. 88).

The only known Fermat primes are

F_0=3
(7)
F_1=5
(8)
F_2=17
(9)
F_3=257
(10)
F_4=65537
(11)

(OEIS A019434), and it seems unlikely that any more will be found using current computational methods and hardware.

Factoring Fermat numbers is extremely difficult as a result of their large size. In fact, as of 2022, only F_5 to F_(11) have been completely factored. 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, ... (OEIS A046052). Written out explicitly, the complete factorizations are

F_5=641·6700417
(12)
F_6=274177·67280421310721
(13)
F_7=59649589127497217·5704689200685129054721
(14)
F_8=1238926361552897·93461639715357977769163558199606896584051237541638188580280321
(15)
F_9=2424833·7455602825647884208337395736200454918783366342657·P99
(16)
F_(10)=45592577·6487031809·4659775785220018543264560743076778192897·P252
(17)
F_(11)=319489·974849·167988556341760475137·3560841906445833920513·P564
(18)

(OEIS A050922). Here, the final large prime is not explicitly given since it can be computed by dividing F_n by the other given factors.

The smallest factors of the Fermat numbers are 5, 17, 257, 65537, 641, 274177, 59649589127497217, 1238926361552897, 2424833, ... (OEIS A093179), while the largest are 5, 17, 257, 65537, 6700417, 67280421310721, 5704689200685129054721, (OEIS A070592).

The following table summarizes the properties of these completely factored Fermat numbers. Other 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). A current list of the known factors of Fermat numbers is maintained by Keller. In these tables, since all factors are of the form k2^n+1, the known factors are expressed in the concise form (k,n).

F_ndigitsfactorsdigitsreference
51023, 7Euler 1732
62026, 14Landry 1880
739217, 22Morrison and Brillhart 1975
878216, 62Brent and Pollard 1981
915537, 49, 99Manasse and Lenstra (In Cipra 1993)
1030948, 10, 40, 252Brent 1995
1161756, 6, 21, 22, 564Brent 1988

As of 2022, F_(12) has 6 known factors with C1133 remaining (where Cn denotes a composite number with n digits), F_(13) has 4 known factors with C2391 remaining, and F_(14) has one known factor with C4880 remaining (Keller).

By the early 1980s, F_n was known to be composite for all 5<=n<=32 with the exceptions n=20, 22, 24, 28, and 31 (Riesel 1994, Crandall et al. 2003). Young and Buell (1988) discovered that F_(20) is composite, Crandall et al. (1995) that F_(22) is composite, and Crandall et al. (2003) that F_(24) is composite (Crandall 1999; Borwein and Bailey 2003, pp. 7-8; Crandall et al. 2003). In 1997, Taura found a small factor of F_(28) (Crandall et al. 2003, Keller), and a small factor of F_(31) was also found. As of 2022, it is known that F_n is composite for all 5<=n<=33 (cf. Crandall et al. 2003).

There are currently two Fermat numbers that are known to be composite, but for which no single factor is known: F_(20) and and F_(24) (Keller; cf. Crandall et al. 2003).

Ribenboim (1996, pp. 89 and 359-360) defines generalized Fermat numbers as numbers of the form a^(2^n)+1 with a>2 even, while Riesel (1994, pp. 102 and 415) defines them more generally as numbers of the form a^(2^n)+b^(2^n).

Fermat numbers satisfy the recurrence relation

F_m=F_0F_1...F_(m-1)+2.
(19)

F_n can be shown to be prime iff it satisfies Pépin's test. Pépin's theorem

3^(2^(2^n-1))=-1 (mod F_n)
(20)

is also both necessary and sufficient.

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

2^(n+1)K+1,
(21)

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
(22)

for n>1. Factors of Fermat numbers are therefore Proth primes since they are of the form k·2^n+1, as long as they also satisfy the additional condition k odd and 2^n>k.

If

F=p_1p_2...p_r
(23)

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

A=3^(F_n-1) (mod F_n)
(24)
B=3^(F-1) (mod F_n)
(25)
R=A-B (mod C).
(26)

Then if R=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...F_n,
(27)

where k is nonnegative and the F_i are zero or more distinct Fermat primes (as stated by Gauss and first published by Wantzel 1836). This is equivalent to the statement that the trigonometric functions sin(kpi/N), cos(kpi/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 last d digits of {F_k,F_(k+1),...} (where k is the smallest integer such that F_k has d digits) are eventually periodic for d=1, 2, ... with periods 1, 4, 20, 100, 500, 2500, ... (OEIS A005054; Koshy 2002-2003).

See also

Cullen Number, Fermat Polynomial, Fermat Prime, Generalized Fermat Number, Near-Square Prime, Pépin's Test, Pépin's Theorem, Pocklington's Theorem, Polygon, Proth Prime, Proth's Theorem, Selfridge-Hurwitz Residue, Woodall Number

Explore with Wolfram|Alpha

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.Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.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.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+/-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.Caldwell, C. K. "The Top Twenty: Fermat Divisors." http://www.utm.edu/research/primes/lists/top20/FermatDivisor.html.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·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. "F24 Resolved--Official Announcement." 29 Sep 1999. http://listserv.nodak.edu/scripts/wa.exe?A2=ind9909&L=nmbrthry&P=2905.Crandall, R.; Doenias, J.; Norrie, C.; and Young, J. "The Twenty-Second Fermat Number is Composite." Math. Comput. 64, 863-868, 1995.Crandall, R. E.; Mayer, E. W.; and Papadopoulos, J. S. "The Twenty-Fourth Fermat Number is Composite." Math. Comput. 72, 1555-1572, 2003.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: Dover, pp. 375-380, 2005.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). Reprinted in Opera Omnia, Series Prima, Vol. 2. Leipzig: Teubner, pp. 1-5, 1915. Translation by J. Bell available at http://www.arxiv.org/abs/math.HO/0501118/.Gardner, M. "Patterns in Primes are a Clue to the Strong Law of Small Numbers." Sci. Amer. 243, 18-28, Dec. 1980.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·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 and 19, 1979.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, p. 200, 1998.Keller, W. "Factor of Fermat Numbers and Large Primes of the Form k·2^n+1." Math. Comput. 41, 661-673, 1983.Keller, W. "Factors of Fermat Numbers and Large Primes of the Form k·2^n+1, II." In prep.Keller, W. "Prime Factors k·2^n+1 of Fermat Numbers F_m and Complete Factoring Status." http://www.prothsearch.net/fermat.html.Koshy, T. "The Ends of a Fermat Number." J. Recr. Math. 31, 183-184, 2002-2003.Kraitchik, M. "Fermat Numbers." §3.6 in Mathematical Recreations. New York: W. W. Norton, pp. 73-75, 1942.Krížek, M.; Luca, F.; and Somer, L. 17 Lectures on Fermat Numbers: From Number Theory to Geometry. New York: Springer-Verlag, 2001.Krížek, M. and Somer, L. "A Necessary and Sufficient Condition for the Primality of Fermat Numbers." Math. Bohem. 126, 541-549, 2001.Landry, F. "Note sur la décomposition du nombre 2^(64)+1 (Extrait)." Comptes Rendus 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.Pólya, G. and Szegö, G. Problem 94, Part 8 in Problems and Theorems in Analysis. Berlin: Springer-Verlag, 1976.Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.Ribenboim, P. "Fermat Numbers" and "Numbers k×2^n+/-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. "Mersenne and Fermat Numbers." Proc. Amer. Math. Soc. 5, 842-846, 1954.Robinson, R. M. "A Report on Primes of the Form k·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.Shorey, T. N. and Stewart, C. L. "On Divisors of Fermat, Fibonacci, Lucas and Lehmer Numbers, 2." J. London Math. Soc. 23, 17-23, 1981.Stewart, C. L. "On Divisors of Fermat, Fibonacci, Lucas and Lehmer Numbers." Proc. London Math. Soc. 35, 425-447, 1977.Sloane, N. J. A. Sequences A000051/M0717, A000215/M2503, A005054, A019434, A046052, A057755, A050922, A070592, A093179, and A114484 in "The On-Line Encyclopedia of Integer Sequences."Trevisan, V. and Carvalho, J. B. "The Composite Character of the Twenty-Second Fermat Number." J. Supercomputing 9, 179-182, 1995.Wantzel, M. L. "Recherches sur les moyens de reconnaître si un problème de géométrie peut se résoudre avec la règle et le compas." J. Math. pures appliq. 1, 366-372, 1836.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.

Referenced on Wolfram|Alpha

Fermat Number

Cite this as:

Weisstein, Eric W. "Fermat Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FermatNumber.html

Subject classifications