nLab
Fermat's little theorem

Contents

Contents

Statement

For xx an integer and pp a prime number, if x0(modp)x \nequiv 0 \pmod{p}, then x p11(modp)x^{p-1} \equiv 1 \pmod{p}.

This useful result is in a sense trivial, since the ring /(p)\mathbb{Z}/(p) is a finite field, with group of units GG of order p1p-1; it is just a matter of recalling x ord(G)=1x^{ord(G)} = 1 for all xx in a finite group GG. For the same reason, a q1=1a^{q-1} = 1 for any nonzero aa in a finite field with qq elements.

Refinements

A stronger result is that the group of units of a finite field with qq elements is cyclic of order q1q-1, or indeed that every finite subgroup of the group of units of any field is cyclic. A proof may be found here.

If AA is a commutative 𝔽 p\mathbb{F}_p-algebra, then the map aa pa \mapsto a^p is an algebra endomorphism σ:AA\sigma: A \to A (the preservation of addition follows easily from the binomial theorem and the fact that (pk)0(modp)\binom{p}{k} \equiv 0 \pmod{p} when 0<k<p0 \lt k \lt p; apparently this is also known as the freshman's dream). It follows that σ:𝔽 q𝔽 q\sigma: \mathbb{F}_q \to \mathbb{F}_q is a field automorphism on a field with q=p kq = p^k elements, since after all

σ k(a)=a p k=a q=a q1a=a\sigma^k(a) = a^{p^k} = a^q = a^{q-1}a = a

for any a𝔽 qa \in \mathbb{F}_q. See also Frobenius automorphism.

Pseudoprimes and Carmichael numbers

Fermat’s little theorem says that in order for a positive integer pp to be prime, it is necessary that a pa(modp)a^p \equiv a \pmod{p} for any integer aa (one may as well assume 0a<p0 \leq a \lt p). This gives a way of showing that an integer nn is not prime (by finding an aa less than nn such that a n11(modn)a^{n-1} \nequiv 1 \pmod{n}) that, especially for large nn, is more efficient than actually factoring nn.

One type of (probabilistic) primality test for pp is to take a base, for example a=2a = 2, and check whether a p1=1(modp)a^{p-1} = 1 \pmod{p}. Chances are good that pp is in fact prime if this is satisfied, although there certainly exist composite numbers which pass this test (called pseudoprimes base aa). The smallest pseudoprime base 22 is 341=1131341 = 11 \cdot 31. One effective primality test for “small” pp (e.g., less than 10 1510^{15}) is to use such a primality test coupled with a table of pseudoprimes.

There are numbers such as n=561=31117n = 561 = 3 \cdot 11 \cdot 17 which are pseudoprimes in any base; these are called Carmichael numbers. A positive integer nn is Carmichael iff it is square-free and for each prime divisor pp of nn, we have that p1p-1 is a divisor of n1n-1. They are comparatively rare, but it is known there are infinitely many (for sufficiently large nn, there are at least n 2/7n^{2/7} Carmichael numbers between 11 and nn).

AKS primality test

A generalization of Fermat’s little theorem can be used to give a deterministic test for primality that can be carried out on any integer nn in “polynomial time” (bounded by a polynomial applied to the number of digits of nn); it was first published only as recently as 2002.

Lemma

An integer n2n \geq 2 is prime if and only if

(xa) nx na(modn)(x-a)^n \equiv x^n - a \pmod{n}

for every or even any aa coprime to nn (so that, for example, the case a=1a=1 would be a sufficient criterion for primality).

Proof

By the argument at freshman’s dream, primality of nn is equivalent to (xa) nx na n(modn)(x-a)^n \equiv x^n - a^n \pmod{n} (for every or any aa), and then primality of nn implies the further reduction a na(modn)a^n \equiv a \pmod{n} by Fermat’s little theorem.

Given an integer rr, and an integer aa relatively prime to rr, let ord r(a)ord_r(a) denote the order of a(modr)a \pmod{r} as a unit in /(r)\mathbb{Z}/(r). We let log(n)log(n) denote the base 22 logarithm of nn, and ϕ\phi denotes the Euler totient function? (so ϕ(r)\phi(r) is the cardinality of the group of units of /(r)\mathbb{Z}/(r)).

Theorem

(Agrawal, Kayal, Saxena) For given nn, let rr be the least positive integer such that ord r(n)>(log(n)) 2ord_r(n) \gt (log(n))^2. Then nn is prime if and only if either

  • nrn \leq r and whenever 1ar1 \leq a \leq r, either 1=gcd(a,n)1 = \gcd(a, n) or n=gcd(a,n)n = \gcd(a, n), or

  • r<nr \lt n and whenever aa is an integer such that 1aϕ(r)log(n)1 \leq a \leq \sqrt{\phi(r)} \cdot log(n), we have

    (xa) nx na(modx r1,n).(x - a)^n \equiv x^n - a \pmod{x^r - 1, n}.

From this result, one can extract an algorithm that decides primality of nn in time bounded by a polynomial in log(n)log(n), invoking help from the following result.

Lemma

For each nn there exists rmax{3,(log(n)) 5}r \leq \max \{3, (log(n))^5\} such that ord r(n)>(log(n)) 2ord_r(n) \gt (log(n))^2.

These results form the basis for the first algorithm for deciding primality that is general (applies to any integer nn), runs in polynomial time, is deterministic (other known efficient tests were randomized and only guaranteed high probability of primality), and unconditional (does not depend on conjectured number-theoretic results such as forms of the Riemann hypothesis).

References

Named after Pierre de Fermat.

  • Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Annals of Mathematics 160 (2) (2004), 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229. (pdf)

Last revised on August 10, 2014 at 05:18:18. See the history of this page for a list of all contributions to it.