How can I prove every integer of the form $6^{3k} + 1$ is composite, where k is a positive integer? If $6^{3k} + 1$ is factorable, then it would be easy to show that it isn't prime. I know I could also represent the formula as $6^{3k} + 1^{3k}$, but the fact that the exponent could be even or odd is giving me some difficulty.
It's easy enough when the exponent is odd as I can treat it as $6^{3k} - ({-1})^{3k}$ and use the difference of powers to factor, but this doesn't apply when the exponent is even. Is there some way I can use sum of cubes to help with it?
 A: You can factorise it as suggested by the comments (which is probably the standard way to answer the question), but you had a very good idea.
Assuming $3k$ is odd, as you noted, we can write:
$$6^{3k} - (-1)^{3k} = (6+1)(6^{3k-1}- 6^{3k-2} + \cdots + 1)$$
Note that, in particular, $7 | (6^{3k} + 1)$ in this case. To derive this another way, note that if $3k$ is odd:
$$6^{3k} + 1 \equiv (-1)^{3k} + 1 \equiv 0 \text{ mod } 7$$
So what do we do if $3k$ is even? Well, note that $2 \nmid 3$, so by Bézout, $2|k$. Hence, we can consider:
$$6^{3k} + 1 = (36)^{3 \cdot \frac{k}{2}} + 1$$
If $3 \cdot \frac{k}{2}$ is odd, then we can apply exactly the same argument. We find that:
$$6^{3k} + 1 = (36)^{3 \cdot \frac{k}{2}} + 1 \equiv (-1)^{3 \cdot \frac{k}{2}}+1 \equiv 0 \text{ mod } 37$$
where you may note that we have chosen $37 = 6^2 + 1$.
By induction, we deduce that if $k = 2^{s} m $ such that $m$ is odd, then:
$$(6^{s+1} + 1) \text{ divides } (6^{3k} + 1)$$
In particular, $6^{3k} + 1$ is not prime.
Remark: note that we used nothing special about $6$, and we only used that $3$ is odd. Thus, the result can be generalised much more broadly.
A: Hint
Remember that $a^3+b^3=(a+b)(a^2-ab+b^2)$. Now call $a=6^k$ and $b=1$.
Can you finish?
