Tricki

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

### Quick description

If is prime and is not a multiple of , then Fermat's little theorem tells us that mod . This gives us a potential way of proving that a number is composite without actually factorizing : all you have to do is find some such that is not a multiple of and mod . 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.

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

### Example 1

Is a prime number? No it isn't, and here is a proof. Let us work out mod by repeated squaring. We find that , , , , , and . Therefore,

It follows that is not a prime.

### General discussion

Of course, trial division would have led us much more quickly to the factorization , 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.