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's little theorem
Summary
Fermat's little theorem states that if p is a prime number, then for any integer a, the number is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
For example, if a = 2 and p = 7, then 27 = 128, and 128 − 2 = 126 = 7 × 18 is an integer multiple of 7.
If a is not divisible by p, that is if a is coprime to p, Fermat's little theorem is equivalent to the statement that ap − 1 − 1 is an integer multiple of p, or in symbols:
For example, if a = 2 and p = 7, then 26 = 64, and 64 − 1 = 63 = 7 × 9 is thus a multiple of 7.
Fermat's little theorem is the basis for the Fermat primality test and is one of the fundamental results of elementary number theory. The theorem is named after Pierre de Fermat, who stated it in 1640. It is called the "little theorem" to distinguish it from Fermat's Last Theorem.
Pierre de Fermat first stated the theorem in a letter dated October 18, 1640, to his friend and confidant Frénicle de Bessy. His formulation is equivalent to the following:
If p is a prime and a is any integer not divisible by p, then a p − 1 − 1 is divisible by p.
Fermat's original statement was
Tout nombre premier mesure infailliblement une des puissances de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.
This may be translated, with explanations and formulas added in brackets for easier understanding, as:
Every prime number [p] divides necessarily one of the powers minus one of any [geometric] progression [a, a2, a3, ...] [that is, there exists t such that p divides at – 1], and the exponent of this power [t] divides the given prime minus one [divides p – 1]. After one has found the first power [t] that satisfies the question, all those whose exponents are multiples of the exponent of the first one satisfy similarly the question [that is, all multiples of the first t have the same property].
Official source
About this result
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.