Proof that $3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2$

Question

This should be rather straightforward, but the goal is to prove that $$3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2.$$ A possibility is to use $$\begin{align*}3^{10^{n+1}}-1&=\left(3^{10^n}-1\right)\left(1+\sum_{k=1}^9 3^{10^n k}\right)\\&=\left(3^{10^n}-1\right)\left(3^{9\cdot 10^n}-1+3^{8\cdot 10^n}-1+\cdots +3^{10^n}-1+10\right),\end{align*}$$ but I don't see how this proves the equality in the question. I got only $$3^{10^{n}}\equiv 1\pmod{3^{10^{n-1}}-1}.$$ Perhaps someone here can explain.

Answer 1

Use induction

Basis $$3^{100}\equiv (3^{10})^{10}$$ $$\equiv 59049^{10}$$ $$\equiv 49^{10}$$ $$\equiv 2401^5$$ $$\equiv 1\pmod {100}$$

Induction hypothesis $$\frac{3^{10^{n}}-1}{10^n}\in\mathbb Z$$

Inductive step $$\frac{3^{10^{n+1}}-1}{10^{n+1}}$$ $$=\frac{3^{10^{n}}-1}{10^n}\times \frac{1+\sum_{k=1}^9 3^{10^nk}}{10}$$ But of the terms multiplied are integers, as the first one directly follows from induction hypothesis and second one by $$\forall 1\leq k\leq 9, 10|10^n|(3^{10^n}-1)|(3^{10^nk}-1)$$ $$\Longrightarrow 3^{10^nk}\equiv 1\pmod {10}\forall 1\leq k\leq 9$$ $$\Longrightarrow 1+\sum_{k=1}^9 3^{10^nk}\equiv 0\pmod {10}$$

Hence proved

Answer 2

Hint

Using the Carmichael function,

$$\lambda(10^n)=5^{n-1}(5-1)2^{n-2}$$ for $n\ge3$

So, if $(a,10)=1,$ $$a^{2^n5^{n-1}}\equiv1\pmod{10^n}$$

Answer 3

The identity you used leads to a proof of the desired result by induction as follows. So suppose that $10^n$ divides $3^{10^n}-1$ for all $n=2,\ldots,N$. Applying the identity yields $$ \frac{3^{10^{N+1}}-1}{3^{10^N}-1}=10 + \sum_{k=1}^9(3^{k\cdot 10^N}-1), $$ and the right side is a multiple of $10$ since each term in the sum is a multiple of $3^{10^N}-1$.

Thus, since $10^N$ divides $3^{10^N}-1$ by the inductive hypothesis, we see that $10^{N+1}$ divides $3^{10^{N+1}}-1$ and this completes the inductive step. All that is left is to check the base case $n=2$, that $3^{100}-1$ is divisible by $100$. This is straightforward using standard modular arithmetic techniques, for instance by checking modulo $4$ and modulo $25$ separately.

Answer 4

Hint:

To get to your goal $3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2,$

can you prove using binomial expansion with $9=10-1$ that $9^{10^{n-1}}\equiv1\mod 10^n $?