Editing TestingPrimality
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Tue Apr 23 23:01:35 2024.
Press
to finish editing.
Who can edit this page?
The World
Members
Council
Admin
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 EQN: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. EQN:2^5-1 is 31, not a multiple of 6. We claim therefore that there are divisors of 6. Consider 15. EQN:2^{14}-1 is 16383 which is not a multiple of 15, so 15 is not prime. But 17? EQN: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!)