#
FAQ: Are all primes (past 2 and 3) of the forms 6*n*+1 and 6*n*-1?

Perhaps the most rediscovered result about primes numbers is the following:

I found that every prime number over 3 lies next to a number divisible by six. Using Matlab with the help of a friend, we wrote a program to test this theory and found that at least within the first 1,000,000 primes this holds true.

Checking a million primes is certainly energetic, but it is not necessary
(and just looking at examples can be misleading in mathematics). Here
is how to prove your observation: take any integer *n* greater than
3, and divide it by 6. That is, write

n= 6q+ r

where *q* is a non-negative integer and the remainder *r* is
one of 0, 1, 2, 3, 4, or 5.

- If the remainder is 0, 2 or 4, then the number
nis divisible by 2, and can not be prime.- If the remainder is 3, then the number
nis divisible by 3, and can not be prime.

So if *n* is prime, then the remainder *r* is either

- 1 (and
n= 6q+ 1 is one more than a multiple of six), or- 5 (and
n= 6q+ 5 = 6(q+1) - 1 is one less than a multiple of six).

Remember that being one more or less than a multiple of six does not
make a number prime. We have only shown that all primes other than
2 and 3 (which divide 6) have this form.

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.