# Fermat's Little Theorem fails for composite instead of prime numbers.

I know Fermat's Little Theorem = Fermat-Euler's Totient Theorem when $n$ is prime.

Elementary Number Theory, Jones, p83 writes

if we simply replace p with a composite integer n, then the resulting congruence $a^{n-1} \equiv 1 \; (mod \, n)$ is not generally true. If gcd(a, n) > 1, then any positive power of a is divisible by d, so it cannot be congruent to 1 mod (n).

Can someone please amplify these 2 sentences? Is there intuition? I tried to prove this -

n composite means $gcd(a,n) > 1$. Dub $gcd(a,n) = g$. By definition of g, $g|a$ and $g|n$.
Thence $g|a \implies g|a^k$ for all $k \ge 1$. Then?

• Same idea as the reverse direction of Wilson's theorem you asked about earlier. If $d$ divides both $a$ and $n$, then it divides $a\bmod n$. And if $d > 1$, then it means that $a\bmod n$ can't be $1$ (or $-1$, for Wilson's theorem). – fkraiem May 10 '14 at 20:49
• More interestingly, for most composite $n$, there exist $a$ with $\gcd(a,n)=1$ such that $a^{n-1}\not\equiv 1\pmod{n}$. This is an important fact for primality testing of huge numbers. But there are exceptions, please see Carmichael Numbers. – André Nicolas May 10 '14 at 21:18
• After your "Then?": $a^k + t\cdot n =$ a multiple of $g$ $\implies a^k \equiv g\cdot s \mod{n}$ but $g\cdot s = 0, g, 2g, \cdots$ never 1. – Anant May 25 '14 at 14:43

If $d | n$ then there is an $r \in \mathbb{Z}$ such that $dr \equiv 0 \mod n$ and $n$ does not divide $r$.
Suppose, by contradiction, there was any integer $a$ such that $ad = 1$. Then $1*r \equiv adr \equiv a*0 \equiv 0 \mod n$ so that $n|r$.
This shows that $d$ cannot have a multiplicative inverse modulo $n$. Thus $d^{n-1} \equiv 1 \mod n$ is impossible since this would imply that $d^{n-2}$ is a multiplicative inverse of $d$ modulo $n$.
To fill in your 'then': "Then: $g|a^k$, and in particular $g|a^{n-1}$. Also, we have $g|n$ (by definition), so $g$ divides any linear combination of $a^{n-1}$ and $n$. Since $a^{n-1}\pmod n$ is such a linear combination (it's $1\cdot a^{n-1}-b\cdot n$, where $b=\lfloor \frac{a^n-1}{n}\rfloor$), then $g|a^{n-1}\pmod n$."