# Why must a and p be relatively prime in Fermat's Little Theorem?

A variant of Fermat's Little Theorem states that $a^{p - 1} \equiv 1~mod~p$ if $a$ is not divisible by $p$.

Why is this last condition important? Why must $a$ and $p$ be relatively prime?

-
If $a$ is divisible by $p$, then $a^{p-1}\equiv 0\pmod p$. – Brian M. Scott May 12 '13 at 4:19
Beat me by 20 seconds @BrianM.Scott ;) – Alex Wertheim May 12 '13 at 4:21

If $p$ divides $a$, then $a\equiv 0\bmod p$, so you will have $$a^{p-1}\equiv 0^{p-1}\equiv 0\not\equiv 1\bmod p.$$ If you prefer a statement of Fermat's little theorem that doesn't have this restriction: $$a^p\equiv a\bmod p$$ for any integer $a$ (regardless of whether it's relatively prime to $p$).
If $a$ is divisible by $p$, then $a^{p-1} \equiv 0$ (mod $p)$.