prove by induction $7 \mid 3^{3^n}+8$ Okay so ive been trying to prove this for about 5 hours... 
really need salvation from the geniouses around here.
prove  by induction
$7\mid 3^{3^n}+8$
i really need some directions on what to do here... 
 A: Hint
The inductive step
$$3^{3^{n+1}}+8= 3^{3\times3^n}+8=\left(3^{3^n}\right)^3+8=(7q-8)^3+8\\=7\times k-8\times 8\times(8-1)=7\times k'$$
A: Suppose it holds for $n$, so that $7|3^{3^n}+8$. For $n+1$, we would like to prove that $7|3^{3^{n+1}}+8$, or equivalently that $7|3^{3^{n}\times 3}+8$, or equivalently that  $7|(3^{3^{n}})^3+8$. From the base ($n$) case, we know that $3^{3^n} \equiv -1 \mod 7$. This allows us to conclude that $(3^{3^{n}})^3+8 \equiv (-1)^3 + 8 \equiv 0\mod 7$.
A: We have to show that :
$$3^{3^n}+8 \equiv 0 \pmod 7 \Rightarrow 3^{3^n}+1 \equiv 0 \pmod 7$$
$$n=1: 3^{3}+1=3^{2+1}+1=3^2 \cdot 3+1=2 \cdot 3+1=7 \equiv 0 \pmod 7 \checkmark$$
$$\text{We suppose that the relation stands for n: }  \ 3^{3^n}+1 \equiv 0 \pmod 7$$
For $n+1$:
$$ 3^{3^{n+1}}+1=3^{3^n \cdot 3}+1 \equiv (3^{3^n})^3+1 \equiv (-1)^3+1 \equiv -1+1 \equiv 0 \pmod 7$$
A: If $x=7a$, what can you say about $(x-8)^3+8$..?
A: First note that this is equivalent to $7$ dividing $3^{3^n}+1$. Clearly if $n=1$, then $3^{3^1}+1 = 28$ and $7$ divides this.
Let's suppose it's true for $n$. Then $3^{3^{n+1}} = 3^{3\cdot3^n} = (3^{3^n})^3$. We want then to show that $7$ divides $(3^{3^n})^3+1$. A nice factorization is that $a^3+b^3 = (a+b)(a^2-ab+b^2)$. So then we can write $(3^{3^n})^3+1$ as $(3^{3^n}+1)((3^{3^n})^2-3^{3^n}+1)$. Can you take it from here?
