Proving a Number is Prime
Date: 10/13/2004 at 23:22:06 From: Amy Subject: Prime Numbers This question was asked previously, but I didn't quite understand the answer. How do you really prove that 2 or some other number is a prime number? I know that a prime number cannot equal to 1 and is only divisible by itself and 1. Proof by induction doesn't make sense for this case, in my opinion, since when n is true, n + 1 is not necessarily a prime. I tried to do proof by contradiction but I wasn't quite sure that it is the right way to go about it. I started out with 2 is not a prime but it doesn't make sense either.
Date: 10/14/2004 at 10:17:02 From: Doctor Vogler Subject: Re: Prime Numbers Hi Amy, Thanks for writing to Dr. Math. You are correct that induction doesn't help. There are, in fact, several ways to prove that a number is prime. But perhaps this is the easiest to understand: A prime number is a number which has exactly TWO (positive integer) factors, namely the number 1 and the prime number itself. So you can prove a number is prime by seeing what numbers divide it. Suppose n is a positive integer, and we want to know if it is prime. We can see if 1 divides n: n / 1 = n, remainder 0 Since the remainder is 0, 1 DOES divide n. In fact, 1 divides every integer. Now we see if 2 divides n. n / 2 = ??? Of course, the answer depends on n. You might get a remainder of 0, which means that 2 divides n, and you might get a remainder of 1, which means that 2 does NOT divide n. Then you try n / 3 = ??? and n / 4 = ??? and so on. You keep going all the way up to n / n = 1, remainder 0. And then you stop, because if you divide n by any number bigger than n (say k > n, so we get n / k = 0, remainder n, then you will NOT get a zero remainder). So now you look at all the factors that you found, including 1 and n and perhaps some others. If there were no others, then n is prime. If there were others, then n is not prime. For example, 2 / 1 = 2, remainder 0 2 / 2 = 1, remainder 0 and no other number divides 2, so there are EXACTLY two factors, namely 1 and 2, which means that 2 is prime. For another example, 3 / 1 = 3, remainder 0 3 / 2 = 1, remainder 1 3 / 3 = 1, remainder 0 and no other number divides 3, so there are EXACTLY two factors, namely 1 and 3, which means that 3 is prime. But, 4 / 1 = 4, remainder 0 4 / 2 = 2, remainder 0 4 / 3 = 1, remainder 1 4 / 4 = 1, remainder 0 and no other number divides 4, so there are THREE factors, namely 1 and 2 and 4, which means that 4 is NOT prime. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 10/14/2004 at 23:59:53 From: Amy Subject: Prime Numbers Thank you so much for answering my problem. But out of curiosity, you said that there are several ways to prove a number is a prime. Can you give me a brief idea of what you mean?
Date: 10/15/2004 at 15:16:34 From: Doctor Vogler Subject: Re: Prime Numbers Hi Amy, Well, for one thing, you don't actually have to check all possible factors. You only need to find any factor that is bigger than 1 and smaller than your number. Furthermore, if the number f is a factor of n, then so is n/f. And one of those two numbers will always be smaller than the square root of n. So you really only have to check the numbers up to the square root of n. And you only have to check prime numbers up to the square root of n because if there is any other factor, then there is a prime factor (the smallest factor bigger than 1 is always a prime factor, in fact). After these improvements, there are more fancy ways to test for prime numbers using properties that prime numbers satisfy, but these are much more complicated and generally require a lot of math to understand. The simplest will actually not tell you if n is prime, but it will usually tell you if n is not prime. It is often called the "Fermat pseudoprimality test" and goes like this: Calculate 2^(n-1) mod n. If you don't get 1 mod n, then n is not prime. This test is based on the so-called "Fermat's Little Theorem." See also Primality Test http://mathforum.org/library/drmath/view/54371.html and search our archives or the internet for "primality test." - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.