Primality TestingDate: 04/22/98 at 00:50:50 From: Matthew Subject: prime numbers Is there any fomula to find if a number is a prime? For example, is there a formula to find out if 1642749328584902 is a prime number? Matthew Date: 04/22/98 at 10:26:29 From: Doctor Wilkinson Subject: Re: prime numbers An excellent question! Of course your example is not prime, because it ends in 2 and all numbers that end in 2 are divisible by 2. There is no simple way to check whether a number is prime, but there are methods that work much better for large numbers than just trying all possible divisors. These methods are too complicated to describe in a short note, but I can give you an idea of how they work. If a number is prime and you take any number that is bigger than one but less than the prime, then it turns out that if you keep multiplying by that number, dividing by the prime and taking the remainder, if you do this one less times than the prime, the result is always 1. For example, 7 is a prime. Start with 3 and call that step 1. Multiply by 3 you get 9. Divide by 7 and take the remainder and you get 2. That's Step 2. Now multiply by 3 and you get 6. Divide by 7 and take the remainder and you still get 6. That's step 3. Continuing: step 4: 6 * 3 = 18; divide by 7, remainder is 4 step 5: 4 * 3 = 12; divide by 7, remainder is 5 step 6: 5 * 3 = 15; divide by 7, remainder is 1 So after 7 - 1 steps you get 1. Now look at it the other way around. Start with a number and suppose you don't know whether it's prime or not. Take a number between 1 and the number and go through the steps I've described. Suppose you don't get a 1. Then you know the number ISN'T a prime. Unfortunately, if you do end up with a 1, you can't say for sure that the number is a prime. But there are fancier versions of this basic idea that will tell you a number is almost certainly a prime if it passes the test. Also, in the version I've described you have to do an awful lot of multiplying and dividing to do the test. But it turns out you can do the test much faster than the way I've described. You may have heard of very large prime numbers being discovered using personal computers. For these numbers, which are a particular kind of number called a "Mersenne number," tests similar to the one I've described will tell you for sure whether the number is prime or not. For more about prime numbers, see the Dr. Math FAQ: http://mathforum.org/dr.math/faq/faq.prime.num.html -Doctors Wilkinson and Sarah, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/