Prove that $n^{n^{n^{n}}}- n^{n^{n}}$ is divisible by $1989$

Problem

Let $n$ be a positive integer with $n \geq 3$. Show that $$n^{n^{n^{n}}}- n^{n^{n}}$$ is divisible by $1989$.

I don't really know where to begin with this question. Maybe I could do some case work on $n$ being even or odd, but I am not sure if that would work or not.

$1989$ factors as $3^2\cdot 13\cdot 17$, so it is enough to show that $n\uparrow\uparrow 4 - n\uparrow\uparrow 3 \equiv 0 \pmod a$ for $a=9,13,17$.

ANALYSIS. Suppose $n$ is coprime to $a$ -- otherwise the congruence clearly holds. Then, $$ n\uparrow\uparrow 4 - n\uparrow\uparrow 3 = n^{n\uparrow\uparrow 2} (n^{n\uparrow\uparrow 3-n\uparrow\uparrow 2} - 1) $$ This will be divisible by $a$ if $$ n^{n\uparrow\uparrow 3-n\uparrow\uparrow 2} \equiv 1 \pmod a $$ which is the case if $$ n\uparrow\uparrow 3 - n\uparrow\uparrow 2 \equiv 0 \pmod{\lambda(a)} $$ When $a=9,13,17$ we have $\lambda(a)=6,12,16$, so it will be enough to show $$ n\uparrow\uparrow 3 - n\uparrow\uparrow 2 \equiv 0 \pmod b \qquad\text{for } b=3, 16$$

Again, we can suppose without loss of generality that $n$ is coprime to $b$ (this wouldn't work if $n=2$, but fortunately we're assuming $n\ge 3$; if $n$ is an even number that is at least $4$, both $n\uparrow\uparrow 3$ and $n\uparrow\uparrow 2$ will be divisible by 16). As before we have $$ n\uparrow\uparrow 3 - n\uparrow\uparrow 2 = n^{n^n}- n^n = n^n (n^{n^n-n} - 1) $$ so we look for a proof that $$ n^n - n \equiv 0 \pmod{\lambda(b)} $$ and $\lambda(b)=2,4$ when $b=3,16$, so we look for $$ n^n-n \equiv 0 \pmod 4 $$ This is not actually true when $n$, is an odd multiple of $2$, but luckily for the $b=16$ case we have already assumed that $n$ is odd, and for $b=3$ we only need $n^n-n$ to be even which is certainly always the case.

Thus we can start SYNTHESIZING a proof from the bottom up:

Lemma 1. $n^n-n$ is always even. Proof. Trivial.

Lemma 2. If $n$ is odd, then $n^n-n \equiv 0 \pmod 4$.

Proof. $n^n-n=n(n^{n-1}-1)$, and since $n-1$ is even, it is a multiple of $\lambda(4)=2$, so $n^{n-1} \equiv 1 \pmod 4$.

Lemma 3. $n^{n^n}-n^n \equiv 0 \pmod 3$.

Proof. This is immediate if $3\mid n$. Otherwise, we have $n^{n^n}-n^n = n^n(n^{n^n-n}-1)$, and $n^n-n$ is even by Lemma 1; since $\lambda(3)=2$ we have $n^{n^n-n}\equiv 1\pmod 3$.

Lemma 4. If $n\ge 3$, then $n^{n^n}-n^n \equiv 0 \pmod{16}$.

Proof. If $n$ is even and $\ge 4$, then this is immediate. Otherwise $n$ is coprime to 16, and we have $n^{n^n}-n^n = n^n(n^{n^n-n}-1)$. By Lemma 2, $n^n-n$ is a multiple of $\lambda(16)=4$, so $n^{n^n-n}\equiv 1\pmod{16}$.

Lemma 5. If $n\ge 3$. then $n^{n^n}-n^n \equiv 0$ modulo $6$, $12$, or $16$.

Proof. By Lemmas 3 and 4.

Lemma 6. If $n\ge 3$, then $n^{n^{n^n}}-n^{n^n} \equiv 0$ modulo $p\in\{13,17\}$.

Proof. This is immediate if $p\mid n$. Otherwise $n^{n^{n^n}}-n^{n^n} = n^{n^n}(n^{(n^{n^n}-n^n)}-1)$, and the exponent $n^{n^n}-n^n$ is a multiple of $\lambda(p)$ by Lemma 5, so $n^{(n^{n^n}-n^n)}\equiv 1\pmod p$.

Lemma 7. If $n\ge 3$, then $n^{n^{n^n}}-n^{n^n} \equiv 0 \bmod9$.

Proof. Immediate if $3\mid n$, since $n^{n^n}$ and $n^n$ are both $\ge 2$. Otherwise, $n$ is coprime to $9$, and the same reasoning as in Lemma 6 applies.

Corollary. If $n\ge 3$, then $n^{n^{n^n}}-n^{n^n} \equiv 0 \bmod{1989}$. Proof. By Lemmas 6 and 7.

We have to show $n\uparrow n\uparrow n\uparrow n\equiv n\uparrow n\uparrow n$ modulo $9,13$ and $17$.

If $n$ is divisible by $3$, the congruence modulo $9$ is trivial. If $n$ is divisible by $13$, the congruence modulo $13$ is trivial, the same for $17$.

So, we can assume that $n$ is coprime to $3\times 13\times 17$. In this case, we have to show $n \uparrow n\uparrow n\equiv n\uparrow n$ modulo $6$, $12$ and $16$. So, modulo $48$ is sufficient.

For even $n\ge 4$, it is easy to show that the congruence holds modulo $16$. If $n$ is odd , we can reduce $n\uparrow n$ and $n$ modulo $8$ and it is easy to see that $n\uparrow n\equiv n$ modulo $8$. The congruence modulo $3$ holds because the second exponent in the power tower is irrelevant.