Redirected from Fermats little theorem
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.
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
This can be further generalized to Carmichael's theorem[?], stated here: http://mathworld.wolfram.com/CarmichaelsTheorem.
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.
Search Encyclopedia
|
Featured Article
|