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?
Asked
Active
Viewed 1,767 times
4
-
3If $a$ is divisible by $p$, then $a^{p-1}\equiv 0\pmod p$. – Brian M. Scott May 12 '13 at 04:19
-
Beat me by 20 seconds @BrianM.Scott ;) – Alex Wertheim May 12 '13 at 04:21
2 Answers
7
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$).
Zev Chonoles
- 129,973
