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

Question

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?

Answer 1

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$."

Answer 2

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

The point is that zero divisors cannot have inverses.

Semi-related to your question is this interesting phenomenon.

Answer 3

Using the following theorem: let $b_1$ and $b_2$ be relatively prime positive integers, and let $z$ and $z'$ be any integers. Then $z\equiv z'\pmod {b_1}$ and $z\equiv z'\pmod {b_2} \iff z\equiv z'\pmod {b_1 b_2}$

From here: let $d=\gcd(a, n) > 1$. This means that
$d$ divides $n$ $\iff$ $n=d*l$ for some integer $l$ and $d$ divides $a$ $\iff$ $n=d*m$ for some integer $m$

Now using the theorem: $a^{n−1} \equiv 1\pmod n \iff a^{n−1} \equiv 1\pmod d$

but $d$ divides $a$ $\implies$ $a^{n−1} \equiv 0 \pmod d$ therefore $a^{n−1} \not\equiv 1\pmod n$