# Why can every prime number be written as 6k±1? [closed]

I want to know how to be sure that each prime number can be written in the form $$6k±1$$. How I can find the prime number that exists after a composite number with this property of prime or other properties of it?

• Could you please clarify what you mean by the second sentence in your question? Do you perhaps mean that, given a composite number of the form $6k±1$, you want to find the smallest prime greater than it? (FWIW, I know of no way substantially better than just generating successive numbers of the form $6k±1$ and running a primality test on each of them.) Or something like that? – Ilmari Karonen Aug 3 '19 at 12:19

Theorem: All prime numbers larger than $$3$$ can be written as $$6k+1$$ or $$6k-1$$ for some natural number $$k$$.
Proof: The remainder of a number modulo $$6$$ is between $$0$$ and $$5$$. If it is $$1$$ or $$5$$, the above criterion holds. It remains to show that, if it is $$0$$, $$2$$, $$3$$ or $$4$$, then the number can not be prime. It is easy to see that, for remainders $$0$$, $$2$$ and $$4$$, the number must be divisible by $$2$$; for remainder $$3$$, it must be divisible by $$3$$. And since the number is not $$2$$ or $$3$$, and is divisible by one of them, it can not be prime. Q.E.D.