Fermat's little theorem

English

Alternative forms

Fermat's Little Theorem

Etymology

Named after French lawyer and amateur mathematician Pierre de Fermat (1601–1665), who stated a version of the theorem in a letter in 1640. Called little to distinguish it from Fermat's Last Theorem.

Proper noun

Fermat's little theorem

(number theory) The theorem that, for any prime number ${\\displaystyle p}$ $\text{[math]}$ and integer ${\\displaystyle a}$ $\text{[math]}$ , ${\\displaystyle a^{p}-a}$ $\text{[math]}$ is an integer multiple of ${\\displaystyle p}$ $\text{[math]}$ .
- 1999, John Stillwell, Translator's introduction, Peter Gustav Lejeune Dirichlet, Richard Dedekind (supplements), Lectures on Number Theory, [1863, P. G. Lejeune Dirichlet, R. Dedekind, Vorlesungen über Zahlentheorie], American Mathematical Society, page xi,
  When combined with the historical remarks made by Gauss himself, they give a bird's eye view of number theory from approximately 1640 to 1840 - from Fermat's little theorem to L-functions - the period which produced the problems and ideas which are still at the center of the subject.
- 1999, Siguna Müller, On the Combined Fermat/Lucas Probable Prime Test, Michael Walker (editor), Cryptography and Coding: 7th IMA International Conference, Springer, LNCS 1746, page 222,
  Most of the pseudoprimality tests originate in some sense on Fermat's Little Theorem aⁿ⁻¹ ≡ 1 mod n.
- 2007, Thomas Koshy, Elementary Number Theory with Applications, Elsevier (Academic Press), 2nd Edition, page 327,
  Incidentally, the special case of Fermat's little theorem for a = 2 was known to the Chinese as early as 500 B.C.
  The first proof of Fermat's little theorem was given by Euler in 1736, almost a century after Fermat's announcement.
- 2008, Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Taylor & Francis (Chapman & Hall/CRC), 2nd Edition, page 189,
  Fermat's little theorem says that if n is prime and gcd(a,n) = 1, then aⁿ⁻¹ ≡ 1 (mod n), so it follows that n must be composite, even though we have not produced a factor.

Usage notes

In the notation of modular arithmetic, ${\\displaystyle a^{p}\\equiv a{\\pmod {p}}}$ . Equivalently, ${\\displaystyle a^{p-1}\\equiv 1{\\pmod {p}}}$ for any ${\\displaystyle a}$ not divisible by ${\\displaystyle p}$ .

Using the theorem in reverse yields a relatively simple but inconclusive test for primality. Composite numbers that satisfy the test form one well-studied class of pseudoprime.

Synonyms

(theorem that a^p − a is divisible by p): Fermat's theorem

Translations

theorem that a^p − a is divisible by p

French: petit théorème de Fermat
Hungarian: kis Fermat-tétel (hu)
Italian: piccolo teorema di Fermat m
Russian: малая теорема Ферма (malaja teorema Ferma)