  Warning: mysql_numrows(): supplied argument is not a valid MySQL result resource in /home/kidsnetau/encyclopedia_content.txt on line 11

Encyclopedia > Fermat's little theorem

Article Content

Fermat's little theorem

Fermat's little theorem states that if p is a prime number, then for any integer a,
$a^p = a \pmod{p}$
This means that if you 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.

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 mn (mod p-1), then aman (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

$a^{\varphi (n)} = 1 \pmod{n}$
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.

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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 July 2002 ... 2002 In Mexico Pope John Paul II canonizes St. Juan Diego an Indian who had a vision of the Virgin Mary, Our Lady of Guadalupe. July 30, 2002 Pope John Paul II ...  