Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a,
This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p (see modular arithmetic). It is called Fermat's little theorem to differentiate it from Fermat's last theorem. Pierre de Fermat found the theorem around 1636; it appeared in one of his letters, dated October 18 1640 to his confidante Frenicle in the following equivalent form: p divides ap-1 - 1 whenever p is prime and a is coprime to p. The case a = 2 was known to the ancient Chinese.
Proofs
Fermat explained his theorem without a proof. The first one who gave a proof was Gottfried Wilhelm Leibniz in a manuscipt without a date, where he wrote also that he knew a proof before 1683.
See Proofs of Fermat's little theorem.
Generalizations
A slight generalization of the theorem, which immediately follows from it, is as follows: if p is prime and m and n are positive integers with m ≡ n (mod p-1), then am ≡ an (mod p) for all integers a. In this form, the theorem is used to justify the RSA public key encryption method.
Fermat's little theorem is generalized by Euler's theorem: for any modulus n and any integer a coprime to n, we have
where φ(n) denotes Euler's φ function counting the integers between 1 and n that are coprime to n. This is indeed a generalization, because if n = p is a prime number, then φ(p) = p - 1.
This can be further generalized to Carmichael's theorem, stated here: http://mathworld.wolfram.com/CarmichaelsTheorem.html.
Pseudoprimes
If a and p are coprime numbers such that ap-1 - 1 is divisible by p, then p need not be prime. If it is not, then p is called a pseudoprime to base a. A number p that is a pseudoprime to base a for every number a coprime to p is called a Carmichael number.
Referenced By
Carmichael number | Cullen number | Cullen prime | Euler's Theorem | Euler-Jacobi pseudoprime | Euler pseudoprime | Fermat | Fermat's Last Theorem | Fermat's theorem | Fermat-Euler theorem | Fermat conjecture | Fermat primality test | FermatsLastTheorem | Fermats Last Theorem | Fermats little theorem:Proofs | Generalized Cullen number | Generalized Cullen prime | Joseph-Louis Lagrange | Joseph-Louis de Lagrange | Joseph Louis Lagrange | Lagrange's Theorem | Lenstra Elliptic Curve Factorization | List of mathematical proofs | List of mathematical topics (D-F) | List of mathematical topics (F-Z) | List of number theory topics | List of proofs | ModularArithmetic | Modular arithmetic | Modulo arithmetic | Number Theory | PierreDeFermat | Pierre de Fermat | Prime number | Prime numbers | Primes | Probable prime | Proofs of Fermat's little theorem | Pseudoprime | RSA Cryptosystem | Theorem of Lagrange | Theory of numbers | Wieferich's criterion | Wieferich prime | Wiles's theorem | Wilson's theorem
|
