$1989 \mid n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$ Before anyone comments, yes this is kind of a duplicate of Prove that $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants to know where I got this problem from here.
I'm looking at the problem $\color{red} {\text{A10}}$. This is not a homework. This is a question I chose to do for fun and I'm totally not sure how to do this problem after playing with for hours. I have made a conjecture that I cannot prove. I believe $n^n \equiv k \mod 1989$ while $n^{n^n} \equiv k \mod 1989$ while $n^{n^{n^n}}\equiv k \mod 1989$ for integer $n \ge 4$. Anyways right now I'm just looking for a hint. I still want to try. You can put spoilers in your answers if you want to. Also we can use whatever we want to prove this. Though I do warn you my number theory skills are still a work in progress. And what I'm looking for is to prove this: $1989 \mid n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$
 A: 
Lemma 1
  $$ \forall n \in \mathbb{N}_{>0} \hspace{1.5em} n^{n^n} \equiv n^n \pmod3 $$

This is trivial.

Lemma 2
  $$\forall n \in \mathbb{N} \hspace{1.5em} n\ge 3 \implies n^{n^n} \equiv n^n \pmod{16} $$

Proof. If $n$ is even, then $n\ge4$ and thus $16 \mid n^n, n^{n^n}$. If $n$ is congruent to $\pm 1$ modulo $16$, the proposition above holds. Then, we only need to check $\pm 3, \pm 5, \pm 7$. By Euler's theorem,
\begin{align}
n\equiv 3 \pmod{16} \implies 3^{n^n} - 3^n &\equiv 3^{n^n-n \pmod8}-1 \\
&\equiv 3^{3^{n\pmod4}-3}-1 \\
&\equiv 3^{3\cdot 8} -1 \equiv 0 \pmod{16}
\end{align}
  \begin{align}
n\equiv 5 \pmod{16} \implies 5^{n^n} - 5^n &\equiv 5^{n^n-n \pmod8}-1 \\
&\equiv 5^{5^{n\pmod4}-5}-1 \equiv 0 \pmod{16}
\end{align}
  \begin{align}
n\equiv 7 \pmod{16} \implies 7^{n^n} - 7^n &\equiv 7^{n^n-n \pmod8}-1 \\
&\equiv 7^{7^{n\pmod4}+1}-1 \\
&\equiv 7^{7^3+1} -1 \equiv 7^{43\cdot 8} -1 \equiv 0 \pmod{16}
\end{align}
The cases $-3,-5,-7$ are now trivial.

Theorem
  $$\forall n \in \mathbb{N} \hspace{1.5em} n\ge 3 \implies n^{n^{n^n}} \equiv n^{n^n} \pmod{1989} $$

Proof. We first split the congruence as follows.
$$\begin{align} n^{n^{n^n}} \equiv n^{n^n} \pmod{1989} &\iff \begin{cases}
n^{n^{n^n}} \equiv n^{n^n} \pmod{9} \\
n^{n^{n^n}} \equiv n^{n^n} \pmod{13} \\
n^{n^{n^n}} \equiv n^{n^n} \pmod{17}
\end{cases} 
\end{align}$$
Since $2,2,3$ are primitive roots of $9,13,17$ respectively, then
$$\begin{align}
n^{n^{n^n}} \equiv n^{n^n} \pmod{9} &\iff \begin{cases}  n^{n^n}\cdot\operatorname{ind}_2n \equiv n^n\cdot\operatorname{ind}_2n \pmod{6} & 3 \nmid n \\ 0 \equiv 0 & 3 \mid n\end{cases} \\[1ex]
n^{n^{n^n}} \equiv n^{n^n} \pmod{13} &\iff \begin{cases}  n^{n^n}\cdot \operatorname{ind}_2n \equiv n^n \cdot\operatorname{ind}_2n \pmod{12} & 13 \nmid n \\ 0 \equiv 0 & 13 \mid n\end{cases} \\[1ex]
n^{n^{n^n}} \equiv n^{n^n} \pmod{17}  &\iff \begin{cases}  n^{n^n}\cdot \operatorname{ind}_3n \equiv n^n \cdot\operatorname{ind}_3n \pmod{16} & 17 \nmid n \\ 0 \equiv 0 & 17 \mid n\end{cases}
\end{align}$$
By the lemmas, these congruences hold for all $n\ge 3$.
A: Note $1989=3^2\cdot 13\cdot 17$. Use Euler's theorem (a.k.a. Euler's totient theorem), namely, let $\varphi(n)$ be the totient function, then,
$$a^{\varphi(n)} \equiv 1 (\text{mod}\, n)$$
for all $a$ relatively prime to $n$. We then have the following result:
$$m|n^a-n^b\Longleftrightarrow \varphi(m)|(a-b),\;\rm{gcd}(n,m)=1\tag1$$
Since $\rm{lcm}[\varphi(3^2),\varphi(13),\varphi(17)]=2^4\cdot 3$,
so we only prove
$$2^4 \cdot3|(n^{n^n}-n^n)$$
and $\rm{lcm}[\varphi(2^4),\varphi(3)]=8$
we only prove
$$8|n^n-n$$
where $n$ is odd. It is clear.
