+0

# induction help

0
117
1
+14

Prove that $$5^{3^{n}} + 1$$ is divisible by $$3^{n + 1}$$ for all nonnegative integers $$n$$.

I've done part of this problem but can't seem to complete it. If you want to see what I've done already just ask

Jun 11, 2020

#1
+8340
0

For the base case: n = 0.

$$\text{When }n = 0,\\ 5^{3^{0}} + 1 = 6\\ 3^{0 + 1} = 3\\ 3|6$$

Assume $$5^{3^k} + 1\text{ is divisible }3^{k + 1}$$.

$$5^{3^{k + 1}} + 1 = 5^{3(3^k)} + 1 = (5^{3^k} + 1)\left(5^{2(3^k)} - 5^{3^k} + 1\right)$$

Now, $$5^{2(3^k)} \equiv 2^{2(3^k)} \equiv 4^{3^k} \equiv 1^{3^k} \equiv 1 \pmod 3$$

$$5^{3^k}\equiv 2^{3^k}\equiv 2^{2K + 1}\equiv 2 \pmod 3$$ for some $$K\in \mathbb Z$$

Therefore $$3|\left(5^{2(3^k)} - 5^{3^k} + 1\right)$$

The proposition is proved.

P.S.: I cheated and used some modular arithmetic ^_^

Jun 11, 2020