<s>[INST] Prove by mathematical induction that $2^{3^n}+1$ is divisible by $3^{n+1}$ 
Prove by mathematical induction that $2^{3^n}+1$ is divisible by $3^{n+1}.$

I'm currently trying to finish a task that requires me to use mathematical induction to prove that $2^{3^n}+1$ is divisible by $3^{n+1}$. This is the first time that the divider is not a simple integer and I'm having trouble trying to prove it. 
This is what I managed to do:

First step:
For $n=1$:
$2^3+1=9$
$3^2=9$
$L=P$
Second step: I assume that for some numbers $n>=1$  $2^{3^n}+1$ is divisible by $3^{n+1}$
Third step: (induction hypothesis):
  $2^{3^{n+1}}+1$ is divisible by $3^{n+1}$

I'm getting stuck here, trying to do some algebra and simplify the dividend:

$2^{3^{n+1}}+1 = 2^{3^n*3}+1$

 [/INST] You should use Wilsons theorem: It says that if $(m,n)=1$ then $m^{\phi(n)}\equiv$ 1 (mod $n$ ), where $\phi(n)$ is the number of natural numbers less than $n$ co-prime to $n$
Using this it follows that $m^{2\cdot 3^n} \equiv 1$ ( mod $3^{n+1}$ ) if $(m,3) = 1$
Now whats left is that $5$ is not a square mod 3 (one can check this easily)
Next it follows $5$ is not a square mod $3^{n+1}$ cause if it were one immediately gets $5$ is a square mod 3
So now we have $5^{2 \cdot 3^n} \equiv $ 1 (mod $3^{n+1}$)
since $5$ is not a square mod $3^{n+1}$ raising it to an odd power also yields a number which is not a square mod $3^{n+1}$ so we get $5^{3^{n}}$ is not a square mod $3^{n+1}$
Since $5^{2 \cdot 3^{n}} \equiv 1 $( mod $3^{n+1}$) we get that 
$5^{3^n} \equiv \pm 1 $ ( mod $3^{n+1}$ ) Now also it cannot equal 1 cause that would imply that $5^{3^n}$ is a square mod $3^{n+1}$ which we have shown is not true.
At last we conclude that $5^{3^n} \equiv$ -1 (mod $3^{n+1}$) so we get the result:
$5^{3^n} + 1 \equiv $ 0 (mod $3^{n+1}$)
If you really want induction then as was said cube and one has:
$5^{3^n} + [3\cdot 5^{n-1}(5^{n-1} +1)] + 1 \equiv $ 0 (mod $3^{n+1}$)
Since by the inductive hypothesis we also have the part in brackets is divisible by $3^{n+1}$ the result follows.
</s>