Determine the number of ten-thousands in $A=5^{5^{5^{5^{5}}}}$.

Determine the number of ten-thousands in $A=5^{5^{5^{5^{5}}}}$.
We are going to determine the remainder of the Euclidean division of A by $10000=$ $2^{5} \times 5^{5}$. We start by dividing by $2^{5}$. Since $\varphi\left(2^{5}\right)=16$, it suffices to determine the remainder of the Euclidean division of $5^{5^{5^{5}}}$ by 16 and finally, since $\varphi(16)=8$, it is necessary to determine the remainder of $5^{5^{5}}$ by 8. And finally $5^{5}$ by 4, which is 1.

So we go back up: $5^{5^{5}} \equiv 5[8], 5^{5^{5^{5}}} \equiv 5^{5} \equiv 13[16]$. And finally, $A \equiv 5^{13} \equiv 5^{5}\left[2^{5}\right]$.

Phew, it turns out that we don't have to redo all the work for $5^{5}$, we immediately have $A \equiv 5^{5}=3125[10000]$. Thus, the ten-thousands digit of A is 0.

Let's return to our pair $(a, n)$ with $a \wedge n=1$. A pertinent question now is to determine for which integers $k \in \mathbb{N}$ we have $a^{k} \wedge 1[n]$. The solution uses the notion of the order of $a$.

The order of $a$ modulo $n$ is the smallest integer $k_{0}$ such that $a^{k_{0}} \wedge 1[n]$. The set of integers $k$ such that $a^{k} \wedge 1[n]$ is exactly the set of multiples of $k_{0}$. Finally, it follows from Euler's theorem that $k_{0} \mid \varphi(n)$.

Indeed, if $k$ satisfies $a^{k} \wedge 1[n]$, we perform the Euclidean division of $k$ by $k_{0}: k=l k_{0}+r$ and we find that

$$
a^{k} \equiv a^{l k_{0}+r} \equiv a^{r} \equiv 1[n]
$$

Thus, by the minimality of $k_{0}$, we must have $r=0$.