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

• there is an answer that makes sense at Yahoo answers.yahoo.com/question/index?qid=20080522123939AAUc4i8 Dec 12, 2015 at 22:54
• I don't really get what he says when he says "Multiplicative group mod17 is cyclic, generator is 3. Therefore we must check divisibily of n^n^n - n^n by 16." Dec 12, 2015 at 22:56
• ok, I did not read that Yahoo answer in detail, but it looked like it made sense (it looked like math :) ... perhaps it doesn't Dec 12, 2015 at 22:59
• I assume he means the group is cyclic of size 16, so $a^{16}=e$ for all $a$. Fermat also explains it though, I think? Dec 12, 2015 at 23:14
• How does know know that "Multiplicative group mod17 is cyclic, generator is 3. Therefore we must check divisibily of n^n^n - n^n by 16"? Dec 12, 2015 at 23:21

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

• sorry λ(16)=8 but you assume it 4 can you explain may be it is just a misunderstanding Aug 8, 2017 at 8:05
• @f.jalili: $\phi(16)=8$, but the Carmichael function $\lambda(16)$ is only $4$. Aug 8, 2017 at 8:21

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.

• What about $19$? That is coprime to $3*13*17$. Dec 12, 2015 at 23:55
• And then, you can use euler's theorem , the exponent can be reduced modulo $\phi(n)$ Dec 12, 2015 at 23:59