For every positive integers $a$ and $n$, is it true that: $a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$?

Question

Based on Fermat's little theorem or on Euler's theorem, is the statement

$$a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$$

true for every positive integers $a$ and $n$?

Answer 1

If $n$ is prime, then this is clearly true: $\text{gcd} (a, p) = 1$ is true for all $a < p$ and Fermat's little theorem does the rest of the work.

However, it is not true for all integers $n$. Take $n = 6$. We have $5^5 \equiv (-1)^5 \equiv -1 \pmod 6$. Indeed, for all even $n>2$, we have $(n-1)^{n-1} \equiv (-1)^{n-1} \equiv -1 \not\equiv 1 \pmod n$