This result came as something of a surprise to me, because it seems so simple yet so final. The reason for it is wonderfully straight-forward: All integers can be represented as 6k+m, where m ε {0, 1, 2, 3, 4, 5}, and k is some integer. This is obvious. Therefore:

m=0: 6k is divisible by 6. Not prime
m=1: 6k+1 has no immediate factors. May be prime.
m=2: 6k+2 = 2 x (3k+1). Not prime
m=3: 6k+3 = 3 x (2k+1). Not prime
m=4: 6k+4 = 2 x (3k+2). Not prime
m=5: 6k+5 has no immediate factors. May be prime.

Therefore the only candidates for primacy are 6k+1 and 6k+5. 6k+5 = 6m-1 for m=k+1. Therefore, all primes are of the form 6n±1 for some integer n.

This result is useful when writing a prime net program for very slow devices (e.g. a graphical calculator), because the program can be saved the overhead of checking obvious multiples of three for primacy. It has other uses, of course, but that one sprang to mind.

Log in or register to write something here or to contact authors.