prove by induction $7 \mid 3^{3^n}+8$

Question

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

Answer 1

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

Answer 2

If $x=7a$, what can you say about $(x-8)^3+8$..?

Answer 3

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

Answer 4

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?

Answer 5

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