Английская Википедия:Fermat's little theorem
Шаблон:Short description Шаблон:For In number theory, Fermat's little theorem states that if Шаблон:Mvar is a prime number, then for any integer Шаблон:Mvar, the number Шаблон:Math is an integer multiple of Шаблон:Mvar. In the notation of modular arithmetic, this is expressed as <math display="block">a^p \equiv a \pmod p.</math>
For example, if Шаблон:Math and Шаблон:Math, then Шаблон:Math, and Шаблон:Math is an integer multiple of Шаблон:Math.
If Шаблон:Mvar is not divisible by Шаблон:Mvar, that is, if Шаблон:Mvar is coprime to Шаблон:Mvar, then Fermat's little theorem is equivalent to the statement that Шаблон:Math is an integer multiple of Шаблон:Mvar, or in symbols:[1][2] <math display="block">a^{p-1} \equiv 1 \pmod p.</math>
For example, if Шаблон:Math and Шаблон:Math, then Шаблон:Math, and Шаблон:Math is thus a multiple of Шаблон:Math.
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.[3]
History
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:[3]
If Шаблон:Mvar is a prime and Шаблон:Mvar is any integer not divisible by Шаблон:Mvar, then Шаблон:Math is divisible by Шаблон:Mvar.
Fermat's original statement was
This may be translated, with explanations and formulas added in brackets for easier understanding, as:
Every prime number [[[:Шаблон:Mvar]]] divides necessarily one of the powers minus one of any [geometric] progression [[[:Шаблон:Math]]] [that is, there exists Шаблон:Mvar such that Шаблон:Mvar divides Шаблон:Math], and the exponent of this power [[[:Шаблон:Mvar]]] divides the given prime minus one [divides Шаблон:Math]. After one has found the first power [[[:Шаблон:Mvar]]] 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 Шаблон:Mvar have the same property].
Fermat did not consider the case where Шаблон:Mvar is a multiple of Шаблон:Mvar nor prove his assertion, only stating:[4]
(And this proposition is generally true for all series [sic] and for all prime numbers; I would send you a demonstration of it, if I did not fear going on for too long.)[5]
Euler provided the first published proof in 1736, in a paper titled "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" in the Proceedings of the St. Petersburg Academy,[6][7] but Leibniz had given virtually the same proof in an unpublished manuscript from sometime before 1683.[3]
The term "Fermat's little theorem" was probably first used in print in 1913 in Zahlentheorie by Kurt Hensel:[8]
(There is a fundamental theorem holding in every finite group, usually called Fermat's little theorem because Fermat was the first to have proved a very special part of it.)
An early use in English occurs in A.A. Albert's Modern Higher Algebra (1937), which refers to "the so-called 'little' Fermat theorem" on page 206.[9]
Further history
Шаблон:Main Some mathematicians independently made the related hypothesis (sometimes incorrectly called the Chinese hypothesis) that Шаблон:Math if and only if Шаблон:Mvar is prime. Indeed, the "if" part is true, and it is a special case of Fermat's little theorem. However, the "only if" part is false: For example, Шаблон:Math, but 341 = 11 × 31 is a pseudoprime to base 2. See below.
Proofs
Шаблон:Main Several proofs of Fermat's little theorem are known. It is frequently proved as a corollary of Euler's theorem.
Generalizations
Euler's theorem is a generalization of Fermat's little theorem: For any modulus Шаблон:Mvar and any integer Шаблон:Mvar coprime to Шаблон:Mvar, one has
<math display="block">a^{\varphi (n)} \equiv 1 \pmod n,</math>
where Шаблон:Math denotes Euler's totient function (which counts the integers from 1 to Шаблон:Mvar that are coprime to Шаблон:Mvar). Fermat's little theorem is indeed a special case, because if Шаблон:Mvar is a prime number, then Шаблон:Math.
A corollary of Euler's theorem is: For every positive integer Шаблон:Mvar, if the integer Шаблон:Mvar is coprime with Шаблон:Mvar, then <math display="block">x \equiv y \pmod{\varphi(n)}\quad\text{implies}\quad a^x \equiv a^y \pmod n, </math> for any integers Шаблон:Mvar and Шаблон:Mvar. This follows from Euler's theorem, since, if <math>x \equiv y \pmod{\varphi(n)}</math>, then Шаблон:Math for some integer Шаблон:Mvar, and one has <math display="block">a^x = a^{y + \varphi(n)k} = a^y (a^{\varphi(n)})^k \equiv a^y 1^k \equiv a^y \pmod n.</math>
If Шаблон:Mvar is prime, this is also a corollary of Fermat's little theorem. This is widely used in modular arithmetic, because this allows reducing modular exponentiation with large exponents to exponents smaller than Шаблон:Mvar.
Euler's theorem is used with Шаблон:Mvar not prime in public-key cryptography, specifically in the RSA cryptosystem, typically in the following way:[10] if <math display="block">y=x^e\pmod n,</math> retrieving Шаблон:Mvar from the values of Шаблон:Mvar, Шаблон:Mvar and Шаблон:Mvar is easy if one knows Шаблон:Math.[11] In fact, the extended Euclidean algorithm allows computing the modular inverse of Шаблон:Mvar modulo Шаблон:Math, that is, the integer Шаблон:Mvar such that <math display="block">ef\equiv 1\pmod{\varphi(n)}.</math> It follows that <math display="block">x\equiv x^{ef}\equiv (x^e)^f \equiv y^f \pmod n.</math>
On the other hand, if Шаблон:Math is the product of two distinct prime numbers, then Шаблон:Math. In this case, finding Шаблон:Mvar from Шаблон:Mvar and Шаблон:Mvar is as difficult as computing Шаблон:Math (this has not been proven, but no algorithm is known for computing Шаблон:Mvar without knowing Шаблон:Math). Knowing only Шаблон:Mvar, the computation of Шаблон:Math has essentially the same difficulty as the factorization of Шаблон:Mvar, since Шаблон:Math, and conversely, the factors Шаблон:Mvar and Шаблон:Mvar are the (integer) solutions of the equation Шаблон:Math.
The basic idea of RSA cryptosystem is thus: If a message Шаблон:Mvar is encrypted as Шаблон:Math, using public values of Шаблон:Mvar and Шаблон:Mvar, then, with the current knowledge, it cannot be decrypted without finding the (secret) factors Шаблон:Mvar and Шаблон:Mvar of Шаблон:Mvar.
Fermat's little theorem is also related to the Carmichael function and Carmichael's theorem, as well as to Lagrange's theorem in group theory.
Converse
The converse of Fermat's little theorem is not generally true, as it fails for Carmichael numbers. However, a slightly stronger form of the theorem is true, and it is known as Lehmer's theorem. The theorem is as follows:
If there exists an integer Шаблон:Mvar such that <math display="block"> a^{p-1}\equiv 1\pmod p </math> and for all primes Шаблон:Mvar dividing Шаблон:Math one has <math display="block"> a^{(p-1)/q}\not\equiv 1\pmod p, </math> then Шаблон:Mvar is prime.
This theorem forms the basis for the Lucas primality test, an important primality test, and Pratt's primality certificate.
Pseudoprimes
Шаблон:Main If Шаблон:Mvar and Шаблон:Mvar are coprime numbers such that Шаблон:Math is divisible by Шаблон:Mvar, then Шаблон:Mvar need not be prime. If it is not, then Шаблон:Mvar is called a (Fermat) pseudoprime to base Шаблон:Mvar. The first pseudoprime to base 2 was found in 1820 by Pierre Frédéric Sarrus: 341 = 11 × 31.[12][13]
A number Шаблон:Mvar that is a Fermat pseudoprime to base Шаблон:Mvar for every number Шаблон:Mvar coprime to Шаблон:Mvar is called a Carmichael number. Alternately, any number Шаблон:Mvar satisfying the equality <math display="block">\gcd\left(p, \sum_{a=1}^{p-1} a^{p-1}\right)=1</math> is either a prime or a Carmichael number.
Miller–Rabin primality test
The Miller–Rabin primality test uses the following extension of Fermat's little theorem:[14]
If Шаблон:Mvar is an odd prime and Шаблон:Math with Шаблон:Math and Шаблон:Mvar odd > 0, then for every Шаблон:Mvar coprime to Шаблон:Mvar, either Шаблон:Math or there exists Шаблон:Mvar such that Шаблон:Math and Шаблон:Math.
This result may be deduced from Fermat's little theorem by the fact that, if Шаблон:Mvar is an odd prime, then the integers modulo Шаблон:Mvar form a finite field, in which 1 modulo Шаблон:Mvar has exactly two square roots, 1 and −1 modulo Шаблон:Mvar.
Note that Шаблон:Math holds trivially for Шаблон:Math, because the congruence relation is compatible with exponentiation. And Шаблон:Math holds trivially for Шаблон:Math since Шаблон:Mvar is odd, for the same reason. That is why one usually chooses a random Шаблон:Mvar in the interval Шаблон:Math.
The Miller–Rabin test uses this property in the following way: given an odd integer Шаблон:Mvar for which primality has to be tested, write Шаблон:Math with Шаблон:Math and Шаблон:Mvar odd > 0, and choose a random Шаблон:Mvar such that Шаблон:Math; then compute Шаблон:Math; if Шаблон:Mvar is not 1 nor −1, then square it repeatedly modulo Шаблон:Mvar until you get −1 or have squared Шаблон:Math times. If Шаблон:Math and −1 has not been obtained by squaring, then Шаблон:Mvar is a composite and Шаблон:Mvar is a witness for the compositeness of Шаблон:Mvar. Otherwise, Шаблон:Mvar is a strong probable prime to base a; that is, it may be prime or not. If Шаблон:Mvar is composite, the probability that the test declares it a strong probable prime anyway is at most Шаблон:Frac, in which case Шаблон:Mvar is a strong pseudoprime, and Шаблон:Mvar is a strong liar. Therefore after Шаблон:Mvar non-conclusive random tests, the probability that Шаблон:Mvar is composite is at most 4−k, and may thus be made as low as desired by increasing Шаблон:Mvar.
In summary, the test either proves that a number is composite or asserts that it is prime with a probability of error that may be chosen as low as desired. The test is very simple to implement and computationally more efficient than all known deterministic tests. Therefore, it is generally used before starting a proof of primality.
See also
- Fermat quotient
- Frobenius endomorphism
- [[p-derivation|Шаблон:Mvar-derivation]]
- Fractions with prime denominators: numbers with behavior relating to Fermat's little theorem
- RSA
- Table of congruences
- Modular multiplicative inverse
Notes
References
Further reading
- Paulo Ribenboim (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. Шаблон:ISBN. pp. 22–25, 49.
External links
- Шаблон:Commons category-inline
- János Bolyai and the pseudoprimes (in Hungarian)
- Fermat's Little Theorem at cut-the-knot
- Euler Function and Theorem at cut-the-knot
- Fermat's Little Theorem and Sophie's Proof
- Шаблон:Springer
- Шаблон:MathWorld
- Шаблон:MathWorld
Шаблон:Portal bar Шаблон:Pierre de Fermat Шаблон:Authority control
- ↑ Шаблон:Harvnb.
- ↑ Шаблон:Harvnb.
- ↑ 3,0 3,1 3,2 Шаблон:Harvnb.
- ↑ Шаблон:Citation (in French)
- ↑ Шаблон:Harvnb for the English translation
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Cite book
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Citation
- ↑ If Шаблон:Mvar is not coprime with Шаблон:Mvar, Euler's theorem does not work, but this case is sufficiently rare for not being considered. In fact, if it occurred by chance, this would provide an easy factorization of Шаблон:Mvar, and thus break the considered instance of RSA.
- ↑ Шаблон:Cite OEIS
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
