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

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

• Try a few non-primes $n$, such as $4$ and $6$. – André Nicolas Apr 24 '14 at 22:14
• @André Nicolas: Thanks. What about the values of $a$? – barak manos Apr 24 '14 at 22:15
• Try $n=4$, and $a=3$, Of course $\gcd(a,n)=1$ but $a^{n-1}=3^3\not\equiv 1\pmod{4}$. The same sort of thing will happen with $n=6$ and $a=5$. But in principle one example is enough to show that the assertion is sometimes not true. – André Nicolas Apr 24 '14 at 22:22
• The other direction is always true. If $a^{n-1}\equiv 1\pmod{n}$ then $\gcd(a,n)=1$. Proof is easy. For if $a$ and $n$ had a non-trivial common divisor, that would divide $a^{n-1}$ and $n$, and therefore would divide $1$. – André Nicolas Apr 24 '14 at 22:28
• ie moral of the story is phi(n) doesn't necessarily divide n-1 – Jack Yoon Apr 24 '14 at 22:29

1 Answer

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$

• That answers my question. Thank you. – barak manos Apr 24 '14 at 22:35