General Observation on Prime Numbers

Date: 09/03/2004 at 19:31:48
From: Stanley
Subject: prime numbers

Is it true that all prime numbers greater than 5 are of the form 
6n + 1 or 6n - 1?  I read this on a website, but it's hard to believe.

Date: 09/05/2004 at 15:02:28
From: Doctor Beryllium
Subject: Re: prime numbers

Hi Stanley,

Yes, it is the case that all primes greater than 6 are either of the
form 6k + 1 or 6k - 1.

Consider that we can divide the set of integers into the following 
classes:

  class 0  6k - 1
  class 1  6k 
  class 2  6k + 1
  class 3  6k + 2
  class 4  6k + 3
  class 5  6k + 4
  class 6  6k + 5

Further notice that the the difference between integers of class 0 and 
class 6 is 6 (this is because -1 is congruent to 5 modulo 6).  That 
means that this cycle of integer classes will repeat over and over as 
we count through the integers with increasing values of k.

Now integers of class 1 have 6 as a factor.  Integers of class 3 have 
2 as a factor.  Integers of class 4 have 3 as a factor.  Integers of 
class 5 have 2 as a factor.  This leaves us with the fact that all 
primes must either be from class 2 or class 0 or class 6.  But we know 
integers from class 6 are the same integers as from class 0.

This shows that all primes must be of one of the following forms:

    6k - 1 == 6k + 5    (congruent modulo 6)

        or

    6k + 1

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