<s>[INST] How to prove by induction that $3^{3n}+1$ is divisible by $3^n+1$ for $(n=1,2,...)$ So this is what I've tried:
Checked the statement for $n=1$ - it's valid.
Assume that $3^{3n}+1=k(3^n+1)$ where $k$ is a whole number (for some n). Proving for $n+1$: $$3^{3n+3}+1=3^33^{3n}+1=3^3(3^{3n}+1)-26=3^3k(3^n+1)-26=3^3k(3^n+1)-3^3+1=3^3[k(3^n+1)-1]+1$$ and I'm stuck. Any help please?
 [/INST] As an interesting alternative, note that $x^3 +1 = (x+1)(x^2 - x + 1)$, so setting $x = 3^n$ gives $3^{3n} + 1 = (3^n + 1)(3^{2n} - 3^n + 1)$.
</s>