1
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ What is the relationship between $2^{2\cdot 3^{\large n-1}}$ and $2^{2\cdot 3^{\large n}}$? $\endgroup$
    – anon
    Dec 17, 2017 at 16:38
  • $\begingroup$ 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$ $\endgroup$ Dec 17, 2017 at 16:52

2 Answers 2

2
$\begingroup$

$(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$.

$\endgroup$
0
2
$\begingroup$

$\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}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .