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.