HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Fermat number, named after
Pierre de Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
, who first studied them, is a
positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
of the form :F_ = 2^ + 1, where ''n'' is a
non-negative In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
integer. The first few Fermat numbers are: : 3, 5, 17,
257 __NOTOC__ Year 257 ( CCLVII) was a common year starting on Thursday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Valerianus and Gallienus (or, less frequently, year 10 ...
, 65537, 4294967297, 18446744073709551617, ... . If 2''k'' + 1 is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
and ''k'' > 0, then ''k'' must be a power of 2, so 2''k'' + 1 is a Fermat number; such primes are called Fermat primes. , the only known Fermat primes are ''F''0 = 3, ''F''1 = 5, ''F''2 = 17, ''F''3 = 257, and ''F''4 = 65537 ; heuristics suggest that there are no more.


Basic properties

The Fermat numbers satisfy the following
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
s: : F_ = (F_-1)^+1 : F_ = F_ \cdots F_ + 2 for ''n'' ≥ 1, : F_ = F_ + 2^F_ \cdots F_ : F_ = F_^2 - 2(F_-1)^2 for ''n'' ≥ 2. Each of these relations can be proved by
mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
. From the second equation, we can deduce Goldbach's theorem (named after
Christian Goldbach Christian Goldbach (; ; 18 March 1690 – 20 November 1764) was a German mathematician connected with some important research mainly in number theory; he also studied law and took an interest in and a role in the Russian court. After traveling ...
): no two Fermat numbers share a common integer factor greater than 1. To see this, suppose that 0 ≤ ''i'' < ''j'' and ''F''''i'' and ''F''''j'' have a common factor ''a'' > 1. Then ''a'' divides both :F_ \cdots F_ and ''F''''j''; hence ''a'' divides their difference, 2. Since ''a'' > 1, this forces ''a'' = 2. This is a
contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
, because each Fermat number is clearly odd. As a
corollary In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
, we obtain another proof of the
infinitude Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol . Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions amo ...
of the prime numbers: for each ''F''''n'', choose a prime factor ''p''''n''; then the sequence is an infinite sequence of distinct primes.


Further properties

* No Fermat prime can be expressed as the difference of two ''p''th powers, where ''p'' is an odd prime. * With the exception of ''F''0 and ''F''1, the last digit of a Fermat number is 7. * The sum of the reciprocals of all the Fermat numbers is
irrational Irrationality is cognition, thinking, talking, or acting without inclusion of rationality. It is more specifically described as an action or opinion given through inadequate use of reason, or through emotional distress or cognitive deficiency. T ...
. (
Solomon W. Golomb Solomon Wolf Golomb (; May 30, 1932 – May 1, 2016) was an American mathematician, engineer, and professor of electrical engineering at the University of Southern California, best known for his works on mathematical games. Most notably, he inven ...
, 1963)


Primality

Fermat numbers and Fermat primes were first studied by Pierre de Fermat, who
conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in ...
d that all Fermat numbers are prime. Indeed, the first five Fermat numbers ''F''0, ..., ''F''4 are easily shown to be prime. Fermat's conjecture was refuted by
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
in 1732 when he showed that : F_ = 2^ + 1 = 2^ + 1 = 4294967297 = 641 \times 6700417. Euler proved that every factor of ''F''''n'' must have the form ''k''2''n''+1 + 1 (later improved to ''k''2''n''+2 + 1 by Lucas) for ''n'' ≥ 2. That 641 is a factor of ''F''5 can be deduced from the equalities 641 = 27 × 5 + 1 and 641 = 24 + 54. It follows from the first equality that 27 × 5 ≡ −1 (mod 641) and therefore (raising to the fourth power) that 228 × 54 ≡ 1 (mod 641). On the other hand, the second equality implies that 54 ≡ −24 (mod 641). These
congruences In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
imply that 232 ≡ −1 (mod 641). Fermat was probably aware of the form of the factors later proved by Euler, so it seems curious that he failed to follow through on the straightforward calculation to find the factor. One common explanation is that Fermat made a computational mistake. There are no other known Fermat primes ''F''''n'' with ''n'' > 4, but little is known about Fermat numbers for large ''n''. In fact, each of the following is an open problem: * Is ''F''''n''
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...
for all ''n'' > 4? * Are there infinitely many Fermat primes? ( Eisenstein 1844) * Are there infinitely many composite Fermat numbers? * Does a Fermat number exist that is not square-free? , it is known that ''F''''n'' is composite for , although of these, complete factorizations of ''F''''n'' are known only for , and there are no known prime factors for and . The largest Fermat number known to be composite is ''F''18233954, and its prime factor was discovered in October 2020.


Heuristic arguments

Heuristics suggest that ''F''4 is the last Fermat prime. The
prime number theorem In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying t ...
implies that a random integer in a suitable interval around ''N'' is prime with probability 1/ln ''N''. If one uses the heuristic that a Fermat number is prime with the same probability as a random integer of its size, and that ''F''5, ..., ''F''32 are composite, then the expected number of Fermat primes beyond ''F''4 (or equivalently, beyond ''F''32) should be : \sum_ \frac < \frac \sum_ \frac = \frac 2^ < 3.36 \times 10^. One may interpret this number as an upper bound for the probability that a Fermat prime beyond ''F''4 exists. This argument is not a rigorous proof. For one thing, it assumes that Fermat numbers behave "randomly", but the factors of Fermat numbers have special properties. Boklan and Conway published a more precise analysis suggesting that the probability that there is another Fermat prime is less than one in a billion.


Equivalent conditions

Let F_n=2^+1 be the ''n''th Fermat number. Pépin's test states that for ''n'' > 0, :F_n is prime if and only if 3^\equiv-1\pmod. The expression 3^ can be evaluated modulo F_n by repeated squaring. This makes the test a fast
polynomial-time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
algorithm. But Fermat numbers grow so rapidly that only a handful of them can be tested in a reasonable amount of time and space. There are some tests for numbers of the form ''k''2''m'' + 1, such as factors of Fermat numbers, for primality. :
Proth's theorem In number theory, Proth's theorem is a primality test for Proth numbers. It states that if ''p'' is a Proth number, of the form ''k''2''n'' + 1 with ''k'' odd and ''k'' < 2''n'', and if there exists an
(1878). Let N = k2m + 1 with odd k < 2m. If there is an integer ''a'' such that :: a^ \equiv -1\pmod :then N is prime. Conversely, if the above congruence does not hold, and in addition :: \left(\frac\right)=-1 (See
Jacobi symbol Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
) :then N is composite. If ''N'' = ''F''''n'' > 3, then the above Jacobi symbol is always equal to −1 for ''a'' = 3, and this special case of Proth's theorem is known as Pépin's test. Although Pépin's test and Proth's theorem have been implemented on computers to prove the compositeness of some Fermat numbers, neither test gives a specific nontrivial factor. In fact, no specific prime factors are known for ''n'' = 20 and 24.


Factorization

Because of Fermat numbers' size, it is difficult to factorize or even to check primality. Pépin's test gives a necessary and sufficient condition for primality of Fermat numbers, and can be implemented by modern computers. The
elliptic curve method The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the thi ...
is a fast method for finding small prime divisors of numbers. Distributed computing project ''Fermatsearch'' has found some factors of Fermat numbers. Yves Gallot's proth.exe has been used to find factors of large Fermat numbers.
Édouard Lucas __NOTOC__ François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him. Biography Lucas ...
, improving Euler's above-mentioned result, proved in 1878 that every factor of the Fermat number F_n, with ''n'' at least 2, is of the form k\times2^+1 (see
Proth number A Proth number is a natural number ''N'' of the form N = k \times 2^n +1 where ''k'' and ''n'' are positive integers, ''k'' is odd and 2^n > k. A Proth prime is a Proth number that is prime. They are named after the French mathematician Franço ...
), where ''k'' is a positive integer. By itself, this makes it easy to prove the primality of the known Fermat primes. Factorizations of the first twelve Fermat numbers are: : , only ''F''0 to ''F''11 have been completely factored. The
distributed computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
project Fermat Search is searching for new factors of Fermat numbers. The set of all Fermat factors is A050922 (or, sorted, A023394) in
OEIS The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
. The following factors of Fermat numbers were known before 1950 (since then, digital computers have helped find more factors): , 356 prime factors of Fermat numbers are known, and 312 Fermat numbers are known to be composite. Several new Fermat factors are found each year.


Pseudoprimes and Fermat numbers

Like
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor In mathematics, a divisor of an integer n, also called a factor ...
s of the form 2''p'' − 1, every composite Fermat number is a strong pseudoprime to base 2. This is because all strong pseudoprimes to base 2 are also
Fermat pseudoprime In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Definition Fermat's little theorem states that if ''p'' is prime and ''a'' is coprime to ''p'', then ''a'p''− ...
s - i.e. :2^ \equiv 1 \pmod for all Fermat numbers. In 1904, Cipolla showed that the product of at least two distinct prime or composite Fermat numbers F_ F_ \dots F_, a > b > \dots > s > 1 will be a Fermat pseudoprime to base 2 if and only if 2^s > a .


Other theorems about Fermat numbers

A Fermat number cannot be a perfect number or part of a pair of amicable numbers. The series of reciprocals of all prime divisors of Fermat numbers is convergent. If ''n''''n'' + 1 is prime, there exists an integer ''m'' such that ''n'' = 22''m''. The equation ''n''''n'' + 1 = ''F''(2''m''+''m'') holds in that case. Let the largest prime factor of the Fermat number ''F''''n'' be ''P''(''F''''n''). Then, :P(F_n) \ge 2^(4n+9) + 1.


Relationship to constructible polygons

Carl Friedrich Gauss Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
developed the theory of
Gaussian period In mathematics, in the area of number theory, a Gaussian period is a certain kind of sum of roots of unity. The periods permit explicit calculations in cyclotomic fields connected with Galois theory and with harmonic analysis (discrete Fourier tra ...
s in his '' Disquisitiones Arithmeticae'' and formulated a
sufficient condition In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
for the constructibility of regular polygons. Gauss stated that this condition was also necessary, but never published a proof. Pierre Wantzel gave a full proof of necessity in 1837. The result is known as the Gauss–Wantzel theorem: : An ''n''-sided regular polygon can be constructed with
compass and straightedge In geometry, straightedge-and-compass construction – also known as ruler-and-compass construction, Euclidean construction, or classical construction – is the construction of lengths, angles, and other geometric figures using only an ideali ...
if and only if ''n'' is the product of a power of 2 and distinct Fermat primes: in other words, if and only if ''n'' is of the form ''n'' = 2''k''''p''1''p''2...''p''''s'', where ''k, s'' are nonnegative integers and the ''p''''i'' are distinct Fermat primes. A positive integer ''n'' is of the above form if and only if its
totient In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...
φ(''n'') is a power of 2.


Applications of Fermat numbers


Pseudorandom number generation

Fermat primes are particularly useful in generating pseudo-random sequences of numbers in the range 1 ... ''N'', where ''N'' is a power of 2. The most common method used is to take any seed value between 1 and ''P'' − 1, where ''P'' is a Fermat prime. Now multiply this by a number ''A'', which is greater than the
square root In mathematics, a square root of a number is a number such that ; in other words, a number whose '' square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . ...
of ''P'' and is a primitive root modulo ''P'' (i.e., it is not a
quadratic residue In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic no ...
). Then take the result modulo ''P''. The result is the new value for the RNG. : V_ = (A \times V_j) \bmod P (see
linear congruential generator A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generat ...
, RANDU) This is useful in computer science, since most data structures have members with 2''X'' possible values. For example, a byte has 256 (28) possible values (0–255). Therefore, to fill a byte or bytes with random values, a random number generator that produces values 1–256 can be used, the byte taking the output value −1. Very large Fermat primes are of particular interest in data encryption for this reason. This method produces only
pseudorandom A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Background The generation of random numbers has many uses, such as for rand ...
values, as after ''P'' − 1 repetitions, the sequence repeats. A poorly chosen multiplier can result in the sequence repeating sooner than ''P'' − 1.


Generalized Fermat numbers

Numbers of the form a^ \!\!+ b^ with ''a'', ''b'' any
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
integers, ''a'' > ''b'' > 0, are called generalized Fermat numbers. An odd prime ''p'' is a generalized Fermat number if and only if ''p'' is congruent to 1 (mod 4). (Here we consider only the case ''n'' > 0, so 3 = 2^ \!+ 1 is not a counterexample.) An example of a probable prime of this form is 1215131072 + 242131072 (found by Kellen Shenton). By analogy with the ordinary Fermat numbers, it is common to write generalized Fermat numbers of the form a^ \!\!+ 1 as ''F''''n''(''a''). In this notation, for instance, the number 100,000,001 would be written as ''F''3(10). In the following we shall restrict ourselves to primes of this form, a^ \!\!+ 1, such primes are called "Fermat primes base ''a''". Of course, these primes exist only if ''a'' is
even Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname) * Even (people), an ethnic group from Siberia and Russian Far East **Even language, a language spoken by the Evens * Odd and Even, a solitaire game wh ...
. If we require ''n'' > 0, then Landau's fourth problem asks if there are infinitely many generalized Fermat primes ''Fn''(''a'').


Generalized Fermat primes

Because of the ease of proving their primality, generalized Fermat primes have become in recent years a topic for research within the field of number theory. Many of the largest known primes today are generalized Fermat primes. Generalized Fermat numbers can be prime only for even , because if is odd then every generalized Fermat number will be divisible by 2. The smallest prime number F_n(a) with n>4 is F_5(30), or 3032 + 1. Besides, we can define "half generalized Fermat numbers" for an odd base, a half generalized Fermat number to base ''a'' (for odd ''a'') is \frac, and it is also to be expected that there will be only finitely many half generalized Fermat primes for each odd base. (In the list, the generalized Fermat numbers (F_n(a)) to an even are a^ \!+ 1, for odd , they are \frac. If is a perfect power with an odd exponent , then all generalized Fermat number can be algebraic factored, so they cannot be prime) (For the smallest number n such that F_n(a) is prime, see ) (See for more information (even bases up to 1000), also see for odd bases) (For the smallest prime of the form F_n(a,b) (for odd a+b), see also ) (For the smallest even base such that F_n(a) is prime, see ) The smallest base ''b'' such that ''b''2''n'' + 1 is prime are :2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, 919444, ... The smallest ''k'' such that (2''n'')''k'' + 1 is prime are :1, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 0, 4, 1, ... (The next term is unknown) (also see and ) A more elaborate theory can be used to predict the number of bases for which F_n(a) will be prime for fixed n. The number of generalized Fermat primes can be roughly expected to halve as n is increased by 1.


Largest known generalized Fermat primes

The following is a list of the 5 largest known generalized Fermat primes. The whole top-5 is discovered by participants in the
PrimeGrid PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ...
project. On the
Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin. The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
one can find th
current top 100 generalized Fermat primes


See also

*
Constructible polygon In mathematics, a constructible polygon is a regular polygon that can be constructed with compass and straightedge. For example, a regular pentagon is constructible with compass and straightedge while a regular heptagon is not. There are infinite ...
: which regular polygons are constructible partially depends on Fermat primes. * Double exponential function * Lucas' theorem *
Mersenne prime In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17 ...
*
Pierpont prime In number theory, a Pierpont prime is a prime number of the form 2^u\cdot 3^v + 1\, for some nonnegative integers and . That is, they are the prime numbers for which is 3-smooth. They are named after the mathematician James Pierpont, who us ...
*
Primality test A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whet ...
*
Proth's theorem In number theory, Proth's theorem is a primality test for Proth numbers. It states that if ''p'' is a Proth number, of the form ''k''2''n'' + 1 with ''k'' odd and ''k'' < 2''n'', and if there exists an
*
Pseudoprime A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to ...
*
Sierpiński number In number theory, a Sierpiński number is an odd natural number ''k'' such that k \times 2^n + 1 is composite for all natural numbers ''n''. In 1960, Wacław Sierpiński proved that there are infinitely many odd integers ''k'' which have this pr ...
*
Sylvester's sequence In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are :2, 3, 7, 43, 1807, 3263443, 10650056950807, 11342371305542184 ...


Notes


References

* * * * - This book contains an extensive list of references. * * * * *


External links

* Chris Caldwell
The Prime Glossary: Fermat number
at The
Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin. The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
. * Luigi Morelli
History of Fermat Numbers
* John Cosgrave

* Wilfrid Keller

* * * * Yves Gallot

* Mark S. Manasse
Complete factorization of the ninth Fermat number
(original announcement) * Peyton Hayslette
Largest Known Generalized Fermat Prime Announcement
{{Pierre de Fermat Constructible polygons Articles containing proofs Unsolved problems in number theory Large integers Classes of prime numbers Integer sequences