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?

  • $\begingroup$ 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? $\endgroup$ Aug 3, 2019 at 12:19

1 Answer 1


I am not sure if this question should be considered on topic here, but I will answer anyway.

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.