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/