Why doesn't Fermat's Little theorem work for 4 and 9?

Solution 1:

You can't apply Fermat's theorem: $$a^{p-1} \equiv 1 \pmod p$$

because $9$ is not a prime. However,you can use Euler's theorem:

$$a^{\phi(m)} \equiv 1 \pmod m$$

$$a=4$$

$$m=9$$

$$(a,m)=1$$

$$\phi(9)=\phi(3^2)=3^2 \left (1-\frac{1}{3} \right )=9 \frac{2}{3}=6$$

Therefore:

$$4^6 \equiv 1 \pmod 9$$

Solution 2:

Fermat's Little Theorem is true only if $p$ is prime - the statement is $$a^p \equiv a \mod p$$ for $p$ prime. When $(a,p) = 1$, this is equivalent to the usual formulation of the theorem (we can divide by $a$): $$a^{p-1} \equiv 1 \mod p$$ if $p$ is prime and $(a,p) = 1$. In this case, $9$ is not prime, so the theorem will fail.

There is however a generalisation that works for all integers, usually called the Fermat-Euler Theorem: we define $\phi(n)$ to be the number of integers less than $n$ that are coprime to $n$. Then if $(a,n)=1$, $$a^{\phi(n)} \equiv 1 \mod n$$

We have $\phi(9) = 6$ and indeed, $4^6 \equiv 1 \mod 9$.