Finding the last $17$ digits of $1707 \uparrow \uparrow 1783$.

elementary-number-theorymodular arithmeticprogrammingtetration

The objective is to find the last $17$ digits of : $1707 \uparrow \uparrow 1783$. In other words:

$$
1707 \uparrow \uparrow 1783 \pmod{10^{17}}
$$

where $\uparrow \uparrow$ represents tetration or repeated exponentiation.

I have thought of a process that goes like this:

  • Find $k$ such that:

$$
1707^{k} \equiv 1 \pmod{10^{17}}
$$

  • Since $\text{gcd}(10^{17}, 1707) = 1 \longrightarrow k = \varphi(10^{17}) = 4 \cdot 10^{16}$

  • Store that $k$ and repeat step $1$ for $\pmod{k}$.

After $51$ iterations, $k$ will be continuously $\varphi(1) = 1$ and there's no point in going further.

However I cannot think how to use these $51$ values of $k$ to yield the result. Can one elaborate on how to continue or suggest another method?

Best Answer

For reference the number $1707 \uparrow \uparrow 1783$ uses Knuth's up-arrow notation for tetration. For every $n\in\Bbb{N}$, the number $1707\uparrow\uparrow n$ is the $n$-th term in the sequence $(s_n)_{n\in\Bbb{N}}$ defined by $s_0=1$ and $s_{n+1}=1707^{s_n}$.

To determine the remainder of $s_{1783}=1707 \uparrow \uparrow 1783$ after division by $10^{17}$ we repeatedly use Euler's theorem, which tells us that if $s_{1782}\equiv t_0\pmod{\varphi(10^{17})}$ then $$s_{1783}=1707^{s_{1782}}\equiv1707^{t_0}\pmod{10^{17}}.$$ Repeating the same argument we see that, if $s_{1782-k}\equiv t_k\pmod{\varphi^k(10^{17})}$ then $$s_{1783-k}=1707^{s_{1782-k}}\equiv1707^{t_k}\pmod{\varphi^{k-1}(10^{17})}.$$ Of course for positive integers $a$ and $b$ we have $\varphi(2^a5^b)=2^{a+1}5^{b-1}$, so $$\varphi^k(10^{17})=\begin{cases} 2^{17+k}5^{17-k}&\text{ if }k\leq17,\\ 2^{51-k}&\text{ if }17\leq k\leq51,\\ 1&\text{ if }k\geq51\end{cases},$$ and hence we may take $t_{50}=1$ as $\varphi^{50}(10^{17})=2$ and $s_{1732}\equiv1\pmod{2}$. As $\varphi^{49}(10^{17})=4$ it follows that $$s_{1733}=1707^{s_{1732}}\equiv1707^1\equiv3\pmod{4},$$ and so we may take $t_{49}=3$. Repeating then yields \begin{eqnarray*} t_{49}=s_{1734}&=&1707^{s_{1733}}&\equiv&1707^3&\equiv&3^3\equiv3&\pmod{8},\\ t_{48}=s_{1735}&=&1707^{s_{1734}}&\equiv&1707^3&\equiv&11^3\equiv3&\pmod{16},\\ \vdots\\ t_{18}=s_{1765}&=&1707^{s_{1765}}&\equiv&1707^{5418148179}&\equiv&14008082771&\pmod{2^{34}}, \end{eqnarray*} and now repeat a few more times to compute $t_0=s_{1783}\pmod{10^{17}}$.

Related Question