Associated Topics || Dr. Math Home || Search Dr. Math

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

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.

more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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