$1989 \mid n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

Question

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$

Answer 1

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.

Answer 2

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$.