Encyclopedia > Fermats little theorem

  Article Content

Fermat's little theorem

Redirected from Fermats little theorem

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

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 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

<math>a^{\varphi (n)} = 1 \pmod{n}</math>
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
BBC News 24

... 24 - Wikipedia <<Up     Contents BBC News 24 BBC News 24 is the BBC's 24-hour news television channel. It first broadcast in November 1997 and ...

 
 
 
This page was created in 35.4 ms