Tricki
a repository of mathematical know-how

To establish that n is composite, show that Fermat's little theorem does not hold for n

Quick description

If p is prime and a is not a multiple of p, then Fermat's little theorem tells us that a^{p-1}\equiv 1 mod p. This gives us a potential way of proving that a number n is composite without actually factorizing n: all you have to do is find some a such that a is not a multiple of n and a^{n-1}\not\equiv 1 mod n. The existence of Carmichael numbers means that this cannot always be done, but a generalization of the idea lies behind the most widely used method of testing for primality.

Prerequisites

Elementary number theory, particularly modular arithmetic.

Note iconIncomplete This article is incomplete. A description of the more general method that is used in randomized primality testing is needed.

Example 1

Is 91 a prime number? No it isn't, and here is a proof. Let us work out 2^{90} mod 91 by repeated squaring. We find that 2^2\equiv 4, 2^4\equiv 16, 2^8=256\equiv -17, 2^{16}\equiv 289\equiv 16, 2^{32}\equiv -17, and 2^{64}\equiv 16. Therefore,

2^{90}=2^{64}\times 2^{16}\times 2^{8}\times 2^2\equiv 16\times 16\times(-17)\times 4\equiv(-17)^2\times 4\equiv 16\times 4=64\not\equiv 1.

It follows that 91 is not a prime.

General discussion

Of course, trial division would have led us much more quickly to the factorization 91=7\times 13, but this method is interesting and important because (i) it shows that it is possible to prove that a number is composite without actually finding the factors, which is potentially useful since it seems to be very hard to find factors in general, and (ii) a development of this idea can be used to give a polynomial-time randomized algorithm for determining whether a number is prime.