# Testing Primality

Suppose we want to know if some number n can be written as the product of two other numbers. (Such a number is called "composite") There is a test that can tell us (mostly) if a number is composite, but which doesn't provide a factor. It's this:

We are guaranteed that
if n does not divide  $2^{(n-1)}-1$
then n is composite.

This doesn't work the other way, but this is a case where we know the answer to the "Yes/No" question, without getting the actual answer we want, a factor of n.

As a specific case, consider 6.  $2^5-1$  is 31, not a multiple of 6. We claim therefore that there are divisors of 6. Consider 15.  $2^{14}-1$  is 16383 which is not a multiple of 15, so 15 is not prime. But 17?  $2^{16}-1$  is 65535, which is 17*3855.

The test can tell us a number is composite without providing a factor.

(It doesn't always work in the other direction, so be careful!)