My first problem

Let $p$ be an odd prime, and let $g$ be a positive integer which is a primitive root modulo $p$ , and such that $g^{p-1} \not\equiv 1 \pmod{p^2}$ .

CLAIM 1 Then $g^{\phi(p^k)} \not\equiv 1 \pmod{p^{k+1}}$ for all $k \ge 1$ .

This is proved by induction. The case $k=1$ is given. Suppose that $k \ge 1$ . If $g^{\phi(p^k)} \not\equiv 1 \pmod{p^{k+1}}$ then it follows that $g^{\phi(p^k)} = 1 + up^k$ where $p$ does not divide $u$ . Since $\phi(p^{k+1}) = p\phi(p^k)$ , we deduce that $g^{\phi(p^{k+1})} \; = \; (1 + up^k)^p \; \equiv \; 1 + up^{k+1} \pmod{p^{k+2}}$ and hence $g^{\phi(p^{k+1})} \not\equiv 1 \pmod{p^{k+2}}$ . The result follows by induction.

CLAIM 2 Then $g$ is a primitive root modulo $p^k$ for all $k \ge 1$ .

The case $k=1$ is given. Suppose now that $k \ge 1$ and that the order of $g$ modulo $p^k$ is $\phi(p^k)$ . Let $x$ be the order of $g$ modulo $p^{k+1}$ . Then $g^x \equiv 1 \pmod{p^{k+1}}$ , and so $g^x \equiv 1 \pmod{p^k}$ , so that $\phi(p^k$ ) divides $x$ . On the other hand $x$ must divide $\phi(p^{k+1}) = p\phi(p^k)$ . From Claim 1 we know that $x \neq \phi(p^k)$ , and hence we deduce that $x = \phi(p^{k+1})$ . The result follows by induction.

It is now a simple calculation to show that $g=17$ and $p=5$ satisfy these conditions, so that $17$ is a primitive root modulo $5^k$ for all $k\ge 1$ .

Note that $T_1 - T_0 = 16 = 2^4$ . Suppose that $T_{k+1} \equiv T_k \pmod{2^{k+4}}$ . Then $T_{k+1} \equiv T_k \pmod{\phi(2^{k+5})}$ , and hence $T_{k+2} = 17^{T_{k+1}} \equiv 17^{T_k} = T_{k+1} \pmod{2^{k+5}}$ . Thus we deduce by induction that $T_{k+1} \equiv T_k \pmod{2^{k+4}}$ for all $k \ge 0$ .

Suppose that $T_{k+1} \equiv T_k \pmod{4 \times 5^k}$ . Then $T_{k+1} \equiv T_k \pmod{\phi(5^{k+1})}$ , and hence $T_{k+2} = 17^{T_{k+1}} \equiv 17^{T_k} = T_{k+1} \pmod{5^{k+1}}$ . Since $T_{k+2} \equiv T_{k+1} \equiv 1 \pmod{4}$ , we deduce that $T_{k+2} \equiv T_{k+1} \pmod{4 \times 5^{k+1}}$ . Since the ground step is trivial, we have shown by induction that $T_{k+1} \equiv T_k \pmod{4\times5^k}$ for all $k\ge0$ .

Thus we deduce that $T_{k+1} \equiv T_k \pmod{10^k}$ for all $k \ge 0$ , and hence that $T_k \equiv T_{2017} \pmod{10^{2017}}$ for all $k \ge 2017$ .

---

Suppose it was true that $T_{2017} \equiv T_{2016} \pmod{10^{2017}}$ . Then we know that $T_{2017} \equiv T_{2016} \pmod{5^{2017}}$ , and so $17^{T_{2016}} \equiv 17^{T_{2015}} \pmod{5^{2017}}$ . Since $17$ is a primitive root modulo $5^{2017}$ , we deduce that $T_{2016} \equiv T_{2015} \pmod{\phi(5^{2017})}$ , and hence $T_{2016} \equiv T_{2015} \pmod{5^{2016}}$ . This in turn would imply that $T_{2015} \equiv T_{2014} \pmod{5^{2015}}$ , and so $T_{2014} \equiv T_{2013} \pmod{5^{2014}}$ . Continuing down inductively, we deduce that $T_1 \equiv T_0 \pmod{5}$ , which is not true. Thus it is not the case that $T_{2017} \equiv T_{2016} \pmod{10^{2017}}$ , and so the answer to the question is $\boxed{2017}$ .

More generally, the smallest integer $n$ such that $T_m \equiv T_n \pmod{10^k}$ for all $m \ge n$ is $\boxed{k}$ .

You can actually guess solution with Excel! Not a proof but a quick guess within 5min!

First for k = 2: Create and index column from 1 to 100 (10^k), another column to find mod(17^k,100) (You can avoid large number by referring the previous mod). Notice that at 17^100 mod 100 = 1. So look for the last 2 digit for $17^{17}$ , it's 77. Therefore $17^{17^{17}} \mod 100 = 17^{77} \mod 100$ , which is 77! So at n=2, the circles begins!

Repeat for k =3: Same discovery: When we exponentiate 17 with a power with the last digits "777", we will get a number with the last digits "777" => n=3

See the pattern?

Note: This solution is incorrect. Can you spot the error?

---

$\textbf{Generalization}$

I'll define $\phi^m(t)$ as follows for later use

$\phi^m(t)=\underbrace{\phi(\phi(\dots\phi(t)\dots))}_{m\phantom{c} times}$

Where $\phi$ is Euler's Totient Function

$\textbf{First Case:}$ $k=1$

The smallest $n$ is $1$ because, since $\phi(10)=4$

$T_a=\underbrace{\mathbin{\color{#D61F06}17}^{\mathbin{\color{#3D99F6}17}^{.^{.^{.^{17}}}}}}_{a}\equiv \underbrace{\mathbin{\color{#D61F06}7}^{\mathbin{\color{#3D99F6}1}^{.^{.^{.^{17}}}}}}_{a}\equiv 7 \mod 10$

$\textbf{Second Case:}$ $k=2$

The smallest $n$ is $2$ , in a similar way, since $\phi^2(100)=16$

$T_a=\underbrace{17^{17^{\mathbin{\color{#D61F06}17}^{.^{.^{.^{17}}}}}}}_{a}\equiv \underbrace{17^{17^{\mathbin{\color{#D61F06}1}^{.^{.^{.^{17}}}}}}}_{a}\equiv 17^{17} \mod 100$

$\textbf{General Case:}$ $k\geq 3$

We will evaluate the remainders $\mod 2^k$ and $\mod 5^k$ and then combine using the CRT . We have to find the smallest $m_1,m_2$ such that $17\equiv 1 \mod \phi^{m_1}(2^k)$ and $17\equiv 1 \mod \phi^{m_2}(5^k)$ and then consider the biggest of the two. This is because this generates a $1$ in the tower, so that even if we add more $17$ to it, the remainder won't change

If $k=3$ or $k=4$ , $T_a$ always leaves a remainder of $1 \mod 2^k$ .

If $k>4$ , we have that $\phi^{k-4}(2^k)=\left(\dfrac{1}{2}\right)^{k-4}\cdot 2^k= 2^4=16$

and $17\equiv 1\mod 16$ , so the minimal $n$ is at least $k-4$ , let's check what happens $\mod 5^k$

$\phi^k(5^k)=\dfrac{4}{5}\left(\dfrac{2}{5}\right)^{k-1}\cdot 5^k=2^{k+1}$

$\phi^{2k-3}(5^k)=\phi^{k-3}(\phi^k(5^k))=\phi^{k-3}(2^{k+1})=\left(\dfrac{1}{2}\right)^{k-3}\cdot 2^{k+1}=2^4=16$

And again, $17\equiv 1\mod 16$ , so the minimal $n$ is at least $2k-3$

Since $n\geq 3$ , $2k-3>k-4$ so the answer is $\boxed{2k-3}$

In this particular case we have $k=2017$

$\Longrightarrow n_{min}=2\cdot 2017 - 3 = \boxed{4031}$