**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Fermat number

Summary

In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form
where n is a non-negative integer. The first few Fermat numbers are:
3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ... .
If 2k + 1 is prime and k > 0, then k itself must be a power of 2, so 2k + 1 is a Fermat number; such primes are called Fermat primes. , the only known Fermat primes are F0 = 3, F1 = 5, F2 = 17, F3 = 257, and F4 = 65537 ; heuristics suggest that there are no more.
The Fermat numbers satisfy the following recurrence relations:
for n ≥ 1,
for n ≥ 2. Each of these relations can be proved by mathematical induction. From the second equation, we can deduce Goldbach's theorem (named after Christian Goldbach): no two Fermat numbers share a common integer factor greater than 1. To see this, suppose that 0 ≤ i < j and Fi and Fj have a common factor a > 1. Then a divides both
and Fj; hence a divides their difference, 2. Since a > 1, this forces a = 2. This is a contradiction, because each Fermat number is clearly odd. As a corollary, we obtain another proof of the infinitude of the prime numbers: for each Fn, choose a prime factor pn; then the sequence is an infinite sequence of distinct primes.
No Fermat prime can be expressed as the difference of two pth powers, where p is an odd prime.
With the exception of F0 and F1, the last digit of a Fermat number is 7.
The sum of the reciprocals of all the Fermat numbers is irrational. (Solomon W. Golomb, 1963)
Fermat numbers and Fermat primes were first studied by Pierre de Fermat, who conjectured that all Fermat numbers are prime. Indeed, the first five Fermat numbers F0, ..., F4 are easily shown to be prime. Fermat's conjecture was refuted by Leonhard Euler in 1732 when he showed that
Euler proved that every factor of Fn must have the form k 2n+1 + 1 (later improved to k 2n+2 + 1 by Lucas) for n ≥ 2.
That 641 is a factor of F5 can be deduced from the equalities 641 = 27 × 5 + 1 and 641 = 24 + 54.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (7)

Related publications (12)

Related people (1)

Related concepts (26)

Related lectures (32)

Ontological neighbourhood

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

CS-119(c): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (

MATH-124: Geometry for architects I

Ce cours entend exposer les fondements de la géométrie à un triple titre :
1/ de technique mathématique essentielle au processus de conception du projet,
2/ d'objet privilégié des logiciels de concept

In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

3 (three) is a number, numeral and digit. It is the natural number following 2 and preceding 4, and is the smallest odd prime number and the only prime preceding a square number. It has religious or cultural significance in many societies. The use of three lines to denote the number 3 occurred in many writing systems, including some (like Roman and Chinese numerals) that are still in use. That was also the original representation of 3 in the Brahmic (Indian) numerical notation, its earliest forms aligned vertically.

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 infinitely many constructible polygons, but only 31 with an odd number of sides are known. Some regular polygons are easy to construct with compass and straightedge; others are not.

Complex Numbers: Gauss-Wantzel Theorem

Covers the Gauss-Wantzel Theorem and Fermat prime numbers.

Prime Numbers and Primality Testing

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

Integer Representation: Basics

Explores the basics of integer representation, highlighting the importance of exact representation and practical examples.

Recently, we have established and used the generalized Littlewood theorem concerning contour integrals of the logarithm of an analytical function to obtain a few new criteria equivalent to the Riemann hypothesis. Here, the same theorem is applied to calcul ...

Thomas Mountford, Michael Cranston

In this paper we use the Riemann zeta distribution to give a new proof of the Erdos-Kac Central Limit Theorem. That is, if zeta(s) = Sigma(n >= 1) (1)(s)(n) , s > 1, then we consider the random variable X-s with P(X-s = n) = (1) (zeta) ( ...

We study actions of groups by orientation preserving homeomorphisms on R (or an interval) that are minimal, have solvable germs at +/-infinity and contain a pair of elements of a certain dynamical type. We call such actions coherent. We establish that such ...