Is $n^{800}= 1 \mod{800}$ given that $n$ is relatively prime to 800?

Question

I was playing around with some numbers and it seems that for a lot of numbers that are relatively prime to 800 $$n^{800} = 1 \mod{800}$$ is this true in general, or is it just coincidental? Is it true that $$n^k=1 \mod{k}$$ where $n,k$ are relatively prime?

Answer 1

Nice observation! It is true for $800$ but not in general.

The explanation is given by Carmichael's theorem: $a^{\lambda(m)} \equiv 1 \bmod m$ for all $a$ coprime with $m$.

Since $\lambda(800)=40$, we have $a^{800} = (a^{40})^{20} \equiv 1^{20} = 1 \bmod 800$ for all $a$ coprime with $m$.