Determine the last three digits of
$$ 2019^{2019^{2019}} $$
[Tower rule $a^{m^n}= a^{(m^n)}$.]
Lemma
We first prove a useful lemma. For natural numbers $x,n$, if $\gcd(x,n)=1$ then by Euler's Theorem
$$ x^{\phi(n)} \equiv 1 \pmod n $$
For a natural number $y$, we use the division algorithm to write
$$ y = \bigl (y \text{ div } \phi(n) \times \phi(n) \bigr ) + \bigl (y \text{ mod } \phi(n) \bigr ) $$
where the div and mod operators are integer division and remainder.
This gives us
$$ \begin{align} x^{y} & \equiv x^{\bigl (y \text{ div } \phi(n) \times \phi(n) \bigr ) + \bigl (y \text{ mod } \phi(n) \bigr )} \pmod n \\ \\ & \equiv x^{\bigl (y \text{ div } \phi(n) \times \phi(n) \bigr )} \times x^{(y \text{ mod } \phi(n))} \pmod n \\ \\ & \equiv (x^{\phi(n)})^{(y \text{ div } \phi(n))} \times x^{(y \text{ mod } \phi(n))} \pmod n \\ \\ & \equiv 1 \times x^{(y \text{ mod } \phi(n))} \pmod n \\ \\ & \equiv x^{(y \text{ mod } \phi(n))} \pmod n \end{align} $$
And so if $\gcd(x,n)=1$, then for some natural $y$, we have
$$ x^y \equiv x^{(y \bmod \phi(n))} \pmod n $$
Solution
We need to find the least positive $x$ such that
$$ 2019^{2019^{2019}} \equiv x \pmod {1000} $$
We simplify the base using $2019 \equiv 19 \pmod {1000}$,
$$ x \equiv 19^{2019^{2019}} \pmod {1000} $$
Using the lemma above, and noting $\phi(1000)=400$, we have
$$ x \equiv 19^{(2019^{2019} \bmod 400 )} \pmod {1000} $$
We now focus on that index $(2019^{2019} \bmod 400 )$. This is the least positive $y$ such that
$$ 2019^{2019} \equiv y \pmod {400} $$
We simplify the base using $2019 \equiv 19 \pmod {400}$,
$$ y \equiv 19^{2019} \pmod {400} $$
Using the lemma above, and noting $\phi(400)=160$, we have
$$ \begin{align} y & \equiv 19^{(2019 \bmod 160)} \pmod {400} \\ \\ y & \equiv 19^{99} \pmod {400} \end{align} $$
We now calculate $19^{99} \pmod {400}$, using
- $19^3 \equiv 6859 \equiv 59 \pmod {400}$
- $59^3 \equiv 205379 \equiv 179 \pmod {400}$
- $179^3 \equiv 5735339 \equiv 139 \pmod {400}$
- $139^3 \equiv 2685619 \equiv 19 \pmod {400}$
$$ \begin{align} 19^{99} & \equiv 19^{81} \times 19^{9} \times 19^{9} \pmod {400} \\ \\ & \equiv (19^{3})^{27} \times (19^{3})^3 \times (19^{3})^3 \pmod {400} \\ \\ & \equiv (59^3)^9 \times 59^3 \times 59^3 \pmod {400} \\ \\ & \equiv (179^3)^3 \times 179 \times 179 \pmod {400} \\ \\ & \equiv (139)^3 \times 179 \times 179 \pmod {400} \\ \\ & \equiv (19)^3 \times 179 \times 179 \pmod {400} \\ \\ & \equiv 608779 \pmod {400} \\ \\ & \equiv 379 \pmod {400} \end{align}$$
And so $y = 379$. This gives us
$$ x \equiv 19^{379} \pmod {1000} $$
The same method of calculation as above gives us $x = 179$.
And so
$$ 2019^{2019^{2019}} \equiv 179 \pmod {1000} $$
which means the last three digits of $2019^{2019^{2019}}$ are 179.