Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show any prime of the form $3k+1$ is of the form $6k+1$.

I came up with my own solution that made perfect sense to me, but when I read the text's solution, it argued that for the primes that are of the particular form are $6k+1 = 3(2k)+1$. But doesn't that really say the primes in the form of $3k+1$ are in the form of $6m+1$? It seems to me as though there's some misuse of notation here -- allowing $k = 2k$. So should the exercise be phrased as $6m+1$ instead?

share|cite|improve this question
I think "of the form" is the key phrase here, not equal to. The letter is essentially a dummy variable. – Dan Rust May 3 '13 at 22:49
up vote 6 down vote accepted

I think it would have made more sense to pose the problem as:

"Show that any prime of the form $3n+1$ is of the form $6k + 1$"

to distinguish the integers $n, k$, and allow for subsequently proving this is the case for $n = 2k$: primes of the form $3n + 1 = 3(2k) + 1$ are thus of the form $6k + 1$.

But just like indexing variables, I suspect that "$k$" as used in the actual problem statement was intended to be a "dummy" variable standing in for "some integer", much like $x$ in the expressions "$\forall x P(x)$, and $\forall x Q(x)$" each use $x$ independently of its use in the corresponding assertion. But this is not standard.

share|cite|improve this answer
Yeah, but when they used $k$ in both, it reads that the $k$'s are going to be the same. Is this sort of thing standard notation? – AlanH May 3 '13 at 22:55
The more standard notation would be that of congruence modulo an integer and so 6n+1=3(2k)+1 would more readily be read as $x=1 \mod 6\Rightarrow x=1 \mod 3$ – Dan Rust May 3 '13 at 23:00
I agree with you, AlanH. That's why I suggested the highlighted statement and find it preferable. The problem statement as you posted is ambiguous, perhaps even misleading. I agree with @Daniel Rust, wholeheartedly. – amWhy May 3 '13 at 23:01
@amWhy: Looks like you clarified this one! +1 – Amzoti May 4 '13 at 0:24

Another way to phrase it is "If k is a positive integer such that 3k+1 is prime then k is even".

The proof, of course, is easy: If k is odd, then k=2h+1 for some integer h. But 3k+1 = 3(2h+1)+1 = 6h+4 is even and therefore not prime.

share|cite|improve this answer

The only $k$ for which $3k+1=6k+1$ is $k=0$, which doesn't even give a prime. The statement means "if a prime is a multiple of three plus one, then it is a multiple of six plus one". The $k$ is a dummy variable; although it is not proper to us $k$ twice, the statement is not much clear if you use two different variables.

share|cite|improve this answer

$3n+1=6k+1$ iff $n=2k.$ If $n$ is even, this will always work, but if $n$ is odd, then $3n+1$ is even and thus not prime and there are no solutions and so the statement is true. You can of course extend this to the rational numbers, and then it gives every prime, but that's not very interesting.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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