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.
Elementary number theory, particularly modular arithmetic.
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.
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.