Fermat's little theorem

related topics
{math, number, function}
{work, book, publish}
{god, call, give}
{son, year, death}
{country, population, people}

Fermat's little theorem (so named to distinguish it from Fermat's last theorem) states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p. This can be expressed in the notation of modular arithmetic as follows:

A variant of this theorem is stated in the following form: if p is a prime and a is an integer coprime to p, then a p−1 − 1 will be evenly divisible by p. In the notation of modular arithmetic:

Fermat's little theorem is the basis for the Fermat primality test.

Contents

History

Pierre de Fermat first stated the theorem in a letter dated October 18, 1640 to his friend and confidant Frénicle de Bessy as the following: [1] p divides a p−1 − 1 whenever p is prime and a is coprime to p.

As usual, Fermat did not prove his assertion, only stating:

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

(And this proposition is generally true for all progressions and for all prime numbers; the proof of which I would send to you, if I were not afraid to be too long.)

Euler first published a proof in 1736 in a paper entitled "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio", but Leibniz left virtually the same proof in an unpublished manuscript from sometime before 1683.

The term "Fermat's Little Theorem" was first used in 1913 in Zahlentheorie by Kurt Hensel:

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist."

(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.)

It was first used in English in an article by Irving Kaplansky, "Lucas's Tests for Mersenne Numbers," American Mathematical Monthly, 52 (Apr., 1945).

Further history

Chinese mathematicians independently made the related hypothesis (sometimes called the Chinese Hypothesis) that p is a prime iff 2^p \equiv 2 \pmod{p}\,. It is true that if p is prime, then 2^p \equiv 2 \pmod{p}\,. This is a special case of Fermat's little theorem. However, the converse (if \,2^p \equiv 2 \pmod{p} then p is prime) is false. Therefore, the hypothesis, as a whole, is false (for example, 2^{341} \equiv 2\pmod{341}\,, but 341 = 11 × 31 is a pseudoprime. See below).

Full article ▸

related documents
Tuple
Enriched category
Transfinite induction
Bounded set
String searching algorithm
Dimension (vector space)
Pre-Abelian category
Linear classifier
Floor and ceiling functions
Square-free integer
Elementary function
Banach algebra
Commutator
Twin prime
Möbius inversion formula
Möbius function
Cyclone (programming language)
Burali-Forti paradox
Gaussian integer
PSPACE
Connected space
ElGamal encryption
Fuzzy set
Principal ideal
HMAC
Discrete space
Loss of significance
Caesar cipher
Entailment
Initial and terminal objects