The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

  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)


    6k + 1

- Doctor Beryllium, The Math Forum 
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.