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

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.

• Yes, corrected now. – groundlark Sep 28 '19 at 17:44

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

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.

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

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$$?