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
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search