Primes Greater Than/Less Than Multiples of Six

Date: 01/18/2002 at 16:31:54
From: Riley
Subject: Primes greater than/less than multiples of six.

I seem to remember my math teacher a couple years ago telling me 
about a postulate stating that every prime number was either one more 
or one less than a multiple of six, excluding 2 and 3. I believe she 
said it was unproven (that's why I call it a postulate), and I was 
wondering if you knew whether or not it was indeed proven.

Thanks.

Date: 01/18/2002 at 19:44:43
From: Doctor Paul
Subject: Re: Primes greater than/less than multiples of six.

It has been proven and a proof is really not that hard if you think 
about it the right way:

All integers can be divided into six classes:

   those that are multiples of six
   those that are 1 more than a multiple of six
   those that are 2 more than a multiple of six
   those that are 3 more than a multiple of six
   those that are 4 more than a multiple of six
   those that are 5 more than a multiple of six

All primes except two are odd and any number that is either:

   (1) a multiple of six,
   (2) two more than a multiple of six, or
   (3) four more than a multiple of six 

will be even and hence cannot be prime.

Thus the only kinds of numbers that can possibly be prime (i.e., the 
odd numbers) can be thought of as either:

   one more than a multiple of six
   three more than a multiple of six
   five more than a multiple of six

It's pretty easy to see that any number that is three more than a 
multiple of six must be divisible by three and hence won't be prime 
unless that number is actually three itself.

To see that any number that is three more than a multiple of six must 
be divisible by three, let x be three more than a multiple of six.  
Then

   x = 6*k + 3 for some integer k.

But then x = 6*k + 3 = 3*(2k + 1), so x is divisible by three.

Thus the only possible candidates for prime numbers are: 2, 3, and 
numbers that are either 1 more than a multiple of six or five more 
than a multiple of six.

Notice that a number that is five more than a multiple of six will be 
one less than a multiple of six.

This completes the proof.  

I hope this helps. Please write back if you'd like to talk about this 
more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/