# Fermat's Little Theorem

• Apr 10th 2011, 01:28 PM
zophas
Fermat's Little Theorem
Hi all,
I have just joined this forum hoping to get some help.
I have just recently started playing with Number Theory and I am trying to
get my head around Modular Arithmatic. So I came across Fermat's Little Theorem,
which says that a^p = a (mod p). Why does this seem to work with some values but not with others? 9^7 = 2 (mod 7) or 12^5 = 2 (mod 5) or 8^5 = 3 (mod 5). Am I missing something here? The other form of the theorem a^(p-1) = 1 (mod p) seems to work just fine. Yes and I do know that the values have to be coprime. Can anyone help me get this?
Thanks.
• Apr 10th 2011, 01:39 PM
Chris L T521
Quote:

Originally Posted by zophas
Hi all,
I have just joined this forum hoping to get some help.
I have just recently started playing with Number Theory and I am trying to
get my head around Modular Arithmatic. So I came across Fermat's Little Theorem,
which says that a^p = a (mod p). Why does this seem to work with some values but not with others? 9^7 = 2 (mod 7) or 12^5 = 2 (mod 5) or 8^5 = 3 (mod 5). Am I missing something here? The other form of the theorem a^(p-1) = 1 (mod p) seems to work just fine. Yes and I do know that the values have to be coprime. Can anyone help me get this?
Thanks.

Its all fine..but note that $\displaystyle a\in\{0,1,2,\ldots,p-1\}$ should be true. In other words, $\displaystyle a$ should be a value in the appropriate residue system you're working with.

So in your examples, observe that $\displaystyle 9\equiv 2\pmod{7}$, $\displaystyle 12\equiv 2\pmod 5$ and $\displaystyle 8\equiv 3\pmod{5}$. (*)

Thus, it follows that $\displaystyle 9^7\equiv \boxed{2^7\equiv 2\pmod{7}}$, $\displaystyle 12^5\equiv \boxed{2^5\equiv 2\pmod{5}}$ and $\displaystyle 8^5\equiv\boxed{3^5\equiv 3\pmod{5}}$.

I hope this clarifies things!

EDIT: You could also observe that

$\displaystyle 9^7\equiv 2\pmod{7} \implies 9^7 \equiv 9\pmod{7}$ by what I said in (*).

Similarly, we also see that $\displaystyle 12^5\equiv 2\pmod{5}\implies 12^5\equiv 12\pmod{5}$ and $\displaystyle 8^5\equiv 3\pmod{5}\implies 8^5\equiv 8\pmod{5}$.

The moral of the story: Fermat's Little Theorem holds as long as $\displaystyle \gcd(a,p)=1$. But most solutions will be simplified so that they lie within the residue system $\displaystyle \{0,1,2,\ldots,p-1\}$. So I would recommend simplifying the expression first and then apply Fermat's little theorem.
• Apr 12th 2011, 05:28 AM
zophas
Thank you very much, Chris
I can see that I need a Modular Arithetic for Dummies book.