why does $3^{10^n} \text{ mod } 10^{n+2} = 2 \cdot 10^{n+1}+1$?

Question

For integers n > 1 it seems that: $$3^{10^n} \text{ mod } 10^{n+2} = 2 \cdot 10^{n+1}+1$$

For example, the last 12 digits of $3^{10^{10}}$ are 200000000001.

I have verified that is true at least up to n = 250 and want a way to prove that it is true for all integers n > 1.

It also appears that many more of the last digits of $3^{10^n}$ are the same.

$3^{10^{10}} = \quad ...228442786552200000000001$

$3^{10^{20}} = \quad ...8084427865522000000000000000000001$

Answer 1

You can try induction on $n$.

$$3^{10^n} = k_n10^{n+2}+2\cdot 10^n+1$$

for some integer $k_n$.

It's true for $n=2$, by your calculation. Now assume true for some $n\geq 2$. Then applying the binomial theorem:

Then $$3^{10^{n+1}}=\left(3^{10^n}\right)^{10}=(k_n10^{n+2}+2\cdot 10^n +1)^{10}= C10^{n+3}+(2\cdot 10^n+1)^{10}$$

But $$(2\cdot 10^n+1)^{10}=1+\binom{10}{1}2\cdot 10^n+ \binom{10}{2}2^2\cdot (10^{2n})+\cdots=1+2\cdot 10^{n+1}+C_210^{n+3}$$

Basically, when $n\geq 2$, then $10^{n+3}\mid \binom{10}{i}2^{i}10^{ni}$ for $i\geq 2$. This is because when $i>2$, then $ni\geq n+3$ and when $i=2$, $ni\geq n+2$ and $10\mid\binom{10}{2}\cdot 2^2$.

Answer 2

HINT: Your observation about the ending digits is very useful. If you can prove that the string of digits $2000...0001$ contains a total of $n+2$ digits (including the $1$ at the end) then the number minus $2\cdot10^n+1$ would have $n+2$ zeroes at the end and would thus be divisible by $10^{n+2}$. So if you can prove that all numbers in the form that you mentioned end with a string of $n+2$ digits in the form $$...2000...0001$$ then the rest of the proof comes easily.

Answer 3

$$3^{10^n}=9^{\frac{10^n}{2}}=(10-1)^{\frac{10^n}{2}}$$ $(10-1)^{\frac{10^n}{2}}$ has a binomial expansion in which most terms with powers bigger than or eqaul to $10^{n+2}$ will disappear inside modulo $10^{n+2}$. Remaining terms are: $${{\frac{10^n}{2}} \choose n+1}10^{n+1}-{{\frac{10^n}{2}} \choose n}10^{n}+-...+1$$

Consider these last terms: $$+-...-{{\frac{10^n}{2}} \choose 3}10^{3}+{{\frac{10^n}{2}} \choose 2}10^{2}-{{\frac{10^n}{2}} \choose 1}10^{1}+1$$

Notice that ${{\frac{10^n}{2}} \choose 3}10^{2}$ has $10^{n+2}$ factor which indicates that it is the smallest term that disappears in modulo $10^{n+2}$.

Expanding those last and smallest remaining three terms terms: $$\frac{(5.10^{n-1})(5.10^{n-1}-1)(5.10^{n-1}-2)}{6}10^2-\frac{(5.10^{n-1})(5.10^{n-1}-1)}{2}10+1$$ $$\frac{(5.10^{n-1}-1)(250.10^{n-1}-100)}{6}10^{n}-\frac{15(5.10^{n-1}-1)}{6}10^n+1$$ $$\frac{(5.10^{n-1}-1)(250.10^{n-1}-115)}{6}10^{n}+1$$ $$\frac{1250.10^{2n-2}-825.10^{n-1}+115}{6}10^{n}+1$$ $$\frac{1250.10^{2n-2}-825.10^{n-1}+115}{3}10^{n-1}+1$$ $$\frac{125.10^{3n-2}-825.10^{2n-2}+115.10^{n-1}}{3}+1$$ $$\frac{125.10^{3n-2}+115.10^{n-1}}{3}-275.10^{2n-2}+1$$ Assuming that $2n-2>n+2$, $-275.10^{2n-2}$ will disappear. $$\frac{125.10^{3n-2}+115.10^{n-1}}{3}+1$$ $$\frac{(5.10^{n-1})(25.10^{2n-1}+23)}{3}+1$$

I have come this far. I don't know if I made any mistakes so far, probably did, but maybe you take it from somewhere here and find a solution.

My strategy was a common one in math olympiads; whenever you are given $3^{2n}$, make it $9^{n}$ and then $(10-1)^{n}$ and then expand it and remove terms based on the modulo. I feel like the idea here is similar but I suck at math at this time of the day.