Fermat’s little theorem


Theorem (Fermat’s little theorem).

If a,pZ with p a prime and pa, then

ap-11(modp).

If we take away the condition that pa, then we have the congruence relationPlanetmathPlanetmath

apa(modp)

instead.

Remarks.

  • Although Fermat first noticed this property, he never actually proved it. There are several different ways to directly prove this theorem, but it is really just a corollary of the Euler theorem.

  • More generally, this is a statement about finite fields: if K is a finite field of order q, then aq-1=1 for all 0aK. More succinctly, the group of units in a finite field is cyclic. If q is prime, then we have Fermat’s little theorem.

  • While it is true that p prime implies the congruence relation above, the converseMathworldPlanetmath is false (as hypothesized by ancient Chinese mathematicians). A well-known example of this is provided by setting a=2 and p=341=11×31. It is easy to verify that 23412(mod341). A positive integer p satisfying ap-11(modp) is known as a pseudoprimeMathworldPlanetmathPlanetmath of base a. Fermat little theoremMathworldPlanetmath says that every prime is a pseudoprime of any base not divisible by the prime.

References

Title Fermat’s little theorem
Canonical name FermatsLittleTheorem
Date of creation 2013-03-22 11:45:08
Last modified on 2013-03-22 11:45:08
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Theorem
Classification msc 11-00
Classification msc 16E30
Synonym Fermat’s theorem
Related topic EulerFermatTheorem
Related topic ProofOfEulerFermatTheoremUsingLagrangesTheorem
Related topic FermatsTheoremProof
Related topic PolynomialCongruence