# Prove if $p$ is a prime of the form $3n+1$, then $p$ is also of the form $6m+1$

Prove that if $p$ is a prime of the form $3n+1$, $p$ is also of the form $6m+1$.

I guess one could use the division algorithm for this; but, what's the best method?

-
Well, if $p\equiv 1 \mod(3)$, then what could $p$ be congruent to mod 6? –  user5137 Nov 3 '11 at 21:56
Maybe this will help: $p=3n+1\iff 3|p-1; p=6n+1\iff 6|p-1$. –  Kevin Nov 3 '11 at 21:56

This is obvious since any prime $p>2$ is odd number and hence $3n+1$ is odd. Therefore $3n$ is even and there exist some $m \in \mathbb{N}$ such that $n=2m$.
Well, it is of one of the forms $6m, 6m+1, 6m+2, 6m+3, 6m+4, 6m+5$, as these are the only possible choices. All but $6m+1, 6m+5$ are not prime for all $m \geq 1$, so we can eliminate all of those. If it is of the form $6m + 5$, then it is of the form $3n + 2$ (let $n = 2m$). Our assumption is that it is of the form $3n+1$, so that is not possible. Therefore, it is of the form $6m+1$ for some $m$.