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?
 A: Do you think that every number can be written as $6k+i$ for $0\leq i\leq 5$??? 
Do you think $6k$ can be prime? 
Do you think $6k+2$ can be prime? 
Do you think $6k+3$ is prime? 
Do you think $6k+4$ is prime?
If you have answered all above....
only possibilities would be writing them as other two possibilities :
$6k+1$ and $6k+5$ which is same as $6k\pm 1$
A: Another phrasing for this question coud be, why is it that if we have a prime number $p$, then  $p+1$ or $p-1$ is a multiple of $6$?
The way I see it is that, for a number to be a multiple of 6, it has to be a multiple of $3$ and $2$. For $p>3 \ $,  $p+1$ and $p-1$ are already multiple of $2$, because they are even. To confirm that they also are multiples of $3$, remember that if we sum the digits of a number and obtain a multiple of $3$, then the original number is a multiple of $3$. 
Thus if we sum the digits of $p$, and we repeat the process untill we get $1$ digit, we have $9$ possibilities. The sum is:
1, then substruct $1$ (or add $5$) to get a multiple of $3$
2, then add$1$ (or substruct $5$) to get a multiple of $3$
3, then $p$ wasn't a prime
4, then substruct $1$ (or add $5$) to get a multiple of $3$
5, then add $1$ (or substruct $5$) to get a multiple of $3$
6, then $p$ wasn't a prime
7, then substruct $1$ (or add $5$) to get a multiple of $3$
8, then add $1$ (or substruct $5$) to get a multiple of $3$
9, then $p$ wasn't a prime
A: 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.
A: Suppose $n = 6k+r$, $r\in\{0,2,4\}$. Can you think of any integers that must divide $n$? What does this say about the primality of $n$, for $n$ sufficiently large?
Now what about $n = 6k+3$?
This leaves only $n = 6k\pm 1.$
A: Let me take a crack at the original question:
$$n = a k + b$$ where $a$ and $b$ are constants would be a prime only if $a$ and $b$ don't have a common factors. Now clearly $b = \pm 1$ will always work. Now if you fix $a$, then the count of the numbers that are less than $a$ and co-prime to it is the Euler's totient function $\phi$. Now if $\phi(a)$ is two then there can be only two possible $b$, viz. $1$, $a-1$. Now $6$ is the largest $a$ for which $\phi(a)=2$.
I hope this was the question.
