Why every prime (>3) is represented as $6k\pm1$

Why is every prime (>3) representable as $6k\pm1$? Afterall, by putting values of k, we don't just get primes but also composites. Then why not $2k+1$ or $3k+2$ or $4k+1$ etc. Is it because of probability? Is there a proof for it?

The proposition you're mentioning is this:

If $n \ne 2, 3$ is prime, then there is an integer $k$ such that $n = 6k - 1$ or $n = 6k + 1$.

This is true by showing that all numbers of other forms are not prime:

$$6k = 6 \cdot k$$ $$6k + 2 = 2(3k + 1)$$ $$6k + 3 = 3(2k + 1)$$ $$6k + 4 = 2(3k + 2)$$ It does not say that every number of the form $6k \pm 1$ is prime; this is most certainly false (I think you may have confused the statement with its converse.) We can make analogous statements with $6$ replaced by other numbers:

If $n \ne 2$ is prime, $n$ is of the form $2k + 1$.

If $n \ne 2$ is prime, $n$ is of the form $4k \pm 1$.

and so on.

Afterall, by putting values of k, we don't just get primes but also composites.

You're confusing a statement with its converse. It is not the case that all integers of the form $6k±1$ are prime. But it is the case that all prime numbers except for 2 and 3 have the form $6k±1$.

Why is every prime (>3) representable as 6k±1?

$\forall n \in \mathbb{Z}, n \in \{0, 1, 2, 3, 4, 5\}$ (modulo 6). IOW, all integers must have one of the forms:

• $n = 6k$ is always composite
• $n = 6k + 1$
• $n = 6k + 2 = 2(3k + 1)$ is composite except for $k = 0 \rightarrow n=2$
• $n = 6k + 3 = 3(2k + 1)$ is composite except for $k = 0 \rightarrow n=3$
• $n = 6k + 4 = 2(3k + 2)$ is always composite
• $n =6k + 5$

Thus, with the exception of 2 and 3, all prime numbers are in $\{1, 5\}$ (modulo 6).

Then why not $2k+1$ or $3k+2$ or $4k+1$ etc.

This is the interesting question. There are similar formulas with a modulus other than 6. For example, in the familiar base-ten representation,

• Integers ending in the digits $\{0, 2, 4, 6, 8\}$ are multiples of 2, and thus not prime (except for 2 itself).
• Integers ending in the digits $\{0, 5\}$ are multiples of 5, and thus not primt (except for 5 itself).

Therefore, with the exception of $\{2, 5\}$, the prime divisors of 10, all prime numbers have a final digit ($n$ mod $10$) in $\{1, 3, 7, 9\}$.

In general, for any modulus $m$, an integer $p > m$ can be prime only if $p$ mod $m$ is relatively prime to $m$ (but not vice versa). For various values of $m$, the possible values of $p$ mod $m$ are as follows:

• 2: $\{1\}$
• 3: $\{1, 2\}$
• 4: $\{1, 3\}$
• 5: $\{1, 2, 3, 4\}$
• 6: $\{1, 5\}$
• 7: $\{1, 2, 3, 4, 5, 6\}$
• 8: $\{1, 3, 5, 7\}$
• 9: $\{1, 2, 4, 5, 7, 8\}$
• 10: $\{1, 3, 7, 9\}$
• 11: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$
• 12: $\{1, 5, 7, 11\}$
• 13: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$
• 14: $\{1, 3, 5, 9, 11, 13\}$
• 15: $\{1, 2, 4, 7, 8, 11, 13, 14\}$
• 16: $\{1, 3, 5, 7, 9, 11, 13, 15\}$
• 17: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\}$
• 18: $\{1, 5, 7, 11, 13, 17\}$
• 19: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18\}$
• 20: $\{1, 3, 7, 9, 11, 13, 17, 19\}$
• 21: $\{1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20\}$
• 22: $\{1, 3, 5, 7, 9, 13, 15, 17, 19, 21\}$
• 23: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22\}$
• 24: $\{1, 5, 7, 11, 13, 17, 19, 23\}$
• 25: $\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24\}$
• 26: $\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$
• 27: $\{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26\}$
• 28: $\{1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27\}$
• 29: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28\}$
• 30: $\{1, 7, 11, 13, 17, 19, 23, 29\}$
• 31: $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30\}$
• 32: $\{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31\}$
• 33: $\{1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32\}$
• 34: $\{1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25, 27, 29, 31, 33\}$
• 35: $\{1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34\}$
• 36: $\{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\}$

So, which modulus should we use in describing the set of prime numbers? It would be helpful to have a simple primality test with as few “false positives” as possible.

For example, $m = 31$ is useless because all it tells us is that no prime number is a multiple of 31 (except for 31 itself). The other $\frac{30}{31}$ of $\mathbb{N}$ (my phrasing may annoy cardinality purists, but you know what I mean) is still potential prime.

OTOH, $m = 2$ gives a useful rule: All prime numbers (except for 2) are odd. This is easy to remember, and excludes $\frac{1}{2}$ of $\mathbb{N}$ (again, being informal with cardinality) from being prime.

But we can do better! If $m$ is 6, 12, 18, 24, or 36, then only $\frac{1}{3}$ of natural numbers are potentially prime. And note that the primality tests for $m \in \{12, 18, 24, 36\}$ are just more complicated ways of expressing the rule for $m = 6$. This gives us a simply-expressed superset of the prime numbers.

$\mathbb{P} \subset \{2, 3\} \cup \{n: n \in \{1, 5\} \mod 6\}$

or, equivalently,

$\mathbb{P} \subset \{2, 3\} \cup \{6k ± 1\}$

That's what's so special about 6.

Now, there are choices for $m$ that give a primality test with fewer false positives. For example, $m=30$ has only $\frac{4}{15}$ of numbers being potentially prime. But the rule is harder to remember.