Question

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

Answer 1

When $n=0$, we have

$5^{3^0} + 1 = 5^1 + 1 = 6$

$3^{0 + 1} = 3^1 = 3$

and of course 3 | 6. ("3 divides 6", in case the notation is unfamiliar.)

Suppose this is true for $n=k$, that

$3^{k + 1} \mid 5^{3^k} + 1$

Now for $n=k+1$, we have

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

so we know the left side is at least divisible by $3^{k+1}$ by our assumption.

It remains to show that

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

which is easily done with Fermat's little theorem. It says

$a^p \equiv a \pmod p$

where $p$ is prime and $a$ is any integer. Then for any positive integer $x$,

$5^3 \equiv 5 \pmod 3 \implies (5^3)^x \equiv 5^x \pmod 3$

Furthermore,

$5^{3^k} \equiv 5^{3\times3^{k-1}} \equiv \left(5^{3^{k-1}}\right)^3 \equiv 5^{3^{k-1}} \pmod 3$

which goes all the way down to

$5^{3^k} \equiv 5 \pmod 3$

So, we find that

$\left(5^{3^k}\right)^2 - 5^{3^k} + 1 \equiv 5^2 - 5 + 1 \equiv 21 \equiv 0 \pmod3$

QED