Prove $x^{x^x} \equiv x^x \mod 16$

Question

$x^{x^x} \equiv x^x \pmod{16}$
Prove by a simple and (quite an) elementary proof that the expression above is true for every $x>2$ ($x$ is a natural number).

The question does not have a topic and you can use any basic tool to answer it. I tried using Modulo first, but couldn't quite get the result. I also thought we might have to use the Euler function but I couldn't find the context. I'd be very happy if anyone could give me a clue, direction or a partial solution. :)

Answer 1

As you've stated, the statement for even $x > 2$ is trivial.

Your statement for the odd $x$ is equivalent to showing that for all odd $x \geq 3$, we have $$ \frac{x^{x^x}}{x^x} \equiv x^{x(x^{x-1} - 1)} \equiv 1 \pmod {16}. $$ By Euler's theorem, it suffices to show that for odd $x \geq 3$, $(x^{x-1} - 1)$ is divisible by $8$, which is to say that $$ x^{x-1} \equiv 1 \pmod8. $$ As it turns out, every odd $x$ satisfies $x^2 \equiv 1 \pmod 8$, and it follows that the above (and thus your statement) holds.

---

Another approach: to show that $(x^{x-1} - 1)$ is divisible by $8$, take $x = 2n+1$ to find that $$ x^{x-1} - 1 = ((2n+1)^{n})^2 - 1 = ((2n+1)^n - 1)((2n+1)^n + 1). $$ Since $(2n+1)^n$ is odd, the numbers $(2n+1)^n \pm 1$ must consist of one multiple of $2$ and one multiple of $4$. Thus, their product $x^{x-1} - 1$ is indeed divisible by $8$.