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.

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.

Login or register to post comments
3376 reads