# Fermat's Little Theorem

• Feb 23rd 2010, 12:26 PM
tarheelborn
Fermat's Little Theorem
I am having trouble knowing where to start to use Fermat's Little Theorem to find the least residue of 5^10 (mod 11). Could you please offer some guidance? Thanks.
• Feb 23rd 2010, 12:45 PM
craig
Fermat's Little Theorem states that:

$\displaystyle a^p = a (mod p)$ where p is a prime number.

Dividing both sides by a, we get:

$\displaystyle a^{p-1} = 1 (mod p)$

Compare this to your question, what do you notice?
• Feb 23rd 2010, 01:20 PM
tarheelborn
That worked out nicely for my first simple example. Thanks! But when I encounter a situation like 5^12(mod 11), I am back to square one. Or do I restate 5^12 as 5^10*5^2 (mod 11)? Would this be congruent to 25 * 1(mod 11)?
• Feb 23rd 2010, 01:22 PM
tarheelborn
Oops--duh--5^10 * 5^2 (mod 11) == 5^2 * 1(mod 11) == 3(mod 11). Right?
• Feb 23rd 2010, 06:20 PM
Bacterius
Hello, you want to solve this for $\displaystyle x$ :
$\displaystyle 5^{12} \equiv x \pmod{11}$

By Fermat's Little Theorem, we are left with $\displaystyle 5^2 \equiv x \pmod{11}$. Now, $\displaystyle 5^2 = 25$, and $\displaystyle 25 \equiv 3 \pmod{11}$, so $\displaystyle 5^{12} \equiv 3 \pmod{11}$.

Basically, you want to simplify the difficult calculation $\displaystyle 5^{12}$ until the remaining operations can be done mentally or easily on a calculator. It is up to you to decide whether $\displaystyle 5^2$ can be calculated manually.
• Feb 24th 2010, 11:14 AM
craig
Quote:

Originally Posted by tarheelborn
That worked out nicely for my first simple example. Thanks! But when I encounter a situation like 5^12(mod 11), I am back to square one. Or do I restate 5^12 as 5^10*5^2 (mod 11)? Would this be congruent to 25 * 1(mod 11)?

Yes basically what Bacterius said. You need to simplify as much as possible and then work from there.

Remember though that Fermat's little Theorem only works if p is a prime number.
• Feb 24th 2010, 06:02 PM
Bacterius
Quote:

Remember though that Fermat's little Theorem only works if p is a prime number.
Note that Fermat's Little Theorem is simply one particular case of Euler's Theorem :

$\displaystyle a^{\varphi{(m)}} \equiv 1 \pmod{m}$ iff $\displaystyle gcd(a, m) = 1$. $\displaystyle \varphi{(m)}$ is the Euler totient function, that is, the quantity of numbers that are coprime with $\displaystyle m$. Coincidentally, if $\displaystyle m$ is prime, then $\displaystyle \varphi{(m)} = m - 1$ :D
• Feb 24th 2010, 06:29 PM
Drexel28
Quote:

Originally Posted by Bacterius
Ironically, if $\displaystyle m$ is prime, then $\displaystyle \varphi{(m)} = m - 1$ :D

I don't think "ironically" is the correct word here. It is coincidental that this is the case.
• Feb 24th 2010, 06:38 PM
Bacterius
Effectively, just looked it up on the dictionary (Yes)
It's quite hard to find the words sometimes ...
Forgive my english :(
• Feb 24th 2010, 06:51 PM
Drexel28
Quote:

Originally Posted by Bacterius
Effectively, just looked it up on the dictionary (Yes)
It's quite hard to find the words sometimes ...
Forgive my english :(

Don't be sorry! You're a very contributive member on MHF! You didn't say anything wrong...it was just a note :D
• Feb 24th 2010, 06:56 PM
Bacterius
:)