Testing Primality

	AllPages RecentChanges Links to this page Edit this page Search Entry portal
Advice For New Users

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!)

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout