2
$\begingroup$

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?

  • 3
    Maybe this will help: $p=3n+1\iff 3|p-1; p=6n+1\iff 6|p-1$.2011-11-03

2 Answers 2

8

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$.

4

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$.