1
$\begingroup$

We have \begin{align} 2^{2^{2}} &\mod 10 = 6 \\ 2^{2^{2^2}} &\mod 100 = 36 \\ 2^{2^{2^{2^2}}} &\mod 1000 = 736 \\ 2^{2^{2^{2^{2^{2}}}}} &\mod 10000 = 8736 \\ 2^{2^{2^{2^{2^{2^2}}}}} &\mod 100000 = 48736 \end{align}

I think you get the point. Basically, it seems like $^n2 \equiv ^{n+1}2 \mod 10^{n-2}$ for $n \geq 3$, where $^n 2$ represents tetration. How could one go about proving this?

$\endgroup$
2
$\begingroup$

Let $x_0=4$ and $x_{n+1}=2^{x_n}$. The claim is $x_{n+1}\equiv x_n\pmod{10^n}$. By induction on $n$, we assume $x_{n+1}\equiv x_n\pmod{10^n}$ and we prove $x_{n+2}\equiv x_{n+1}\pmod{10^{n+1}}$.

We have $$x_{n+2}-x_{n+1}=2^{x_{n+1}}-2^{x_n}=2^{x_n}(2^{x_{n+1}-x_n}-1)$$ Since $x_n\geq n+1$ we get $x_{n+2}\equiv x_{n+1}\pmod{2^{n+1}}$. On the other hand for $n\geq 2$ we have $x_{n+1}\equiv x_n\pmod{4}$ and $x_{n+1}\equiv x_n\pmod{5^n}$ by assumption, so that $x_{n+1}-x_n\equiv 0\pmod{4\cdot 5^n}$. Since $\varphi(5^{n+1})=4\cdot 5^n$, this gives $2^{x_{n+1}-x_n}\equiv 1\pmod{5^{n+1}}$, thus giving $x_{n+2}\equiv x_{n+1}\pmod{5^{n+1}}$. This, together with $x_{n+2}\equiv x_{n+1}\pmod{2^{n+1}}$ gives $x_{n+2}\equiv x_{n+1}\pmod{10^{n+1}}$ concluding the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.