# Proving that $2^{2\cdot 3^{n-1}}\equiv 1+3^n\pmod{3^{n+1}}$ for every natural $n$

Prove that $2^{2\cdot 3^{n-1}}\equiv 1+3^n\pmod{3^{n+1}}$ for every natural $n$

Of course, should be done by induction. Base case ($n=1$) is easy.

I got stuck with the step:

Let's assume that it's right for $n$. Then,

$$2^{2\cdot 3^{n-1}} = 1 + 3^n \pmod{3^{n+1}}$$

We want to evaluate $$2^{2 \cdot 3^n} \pmod {3^{n+2}}$$

I think we can somehow utilize the fact that $2,3$ are coprime and reduce $3^{n+2}$ to $3^{n+1}$.

I'd be glad for help on that.

Thanks!

• What is the relationship between $2^{2\cdot 3^{\large n-1}}$ and $2^{2\cdot 3^{\large n}}$?
– anon
Dec 17, 2017 at 16:38
• Well, I thought breaking it to $2^{3^{n}} \cdot 2^{3^{n}}$ and $2^{3^{n}} = 2^{3\cdot 3^{n-1}} = \left( 2^{3^{n-1}} \right)^3$ Dec 17, 2017 at 16:52

$(1+3^nx)^3 = 1+3^{n+1}x+3^{2n+1}x^2+3^{3n}x^3\equiv 1+3^{n+1}x \pmod{3^{n+2}}$ if $n\ge 1$.
\begin{align}2^{2\cdot3^{n-1}}&=(3-1)^{2\cdot3^{n-1}} \\\\ &=3^{n+1}\cdot k-2\cdot3^n+1 \\\\ &=3^{n+1}\cdot k-(3-1)\cdot3^n+1 \\\\ &=3^{n+1}\cdot (k-1)+3^n+1 \\\\ &\equiv3^n+1\pmod{3^{n+1}}\end{align}