# Math Help - Fermat's Little Theorem

1. ## 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.

2. Fermat's Little Theorem states that:

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

Dividing both sides by a, we get:

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

Compare this to your question, what do you notice?

3. 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)?

4. Oops--duh--5^10 * 5^2 (mod 11) == 5^2 * 1(mod 11) == 3(mod 11). Right?

5. Hello, you want to solve this for $x$ :
$5^{12} \equiv x \pmod{11}$

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

Basically, you want to simplify the difficult calculation $5^{12}$ until the remaining operations can be done mentally or easily on a calculator. It is up to you to decide whether $5^2$ can be calculated manually.

6. 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.

7. 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 :

$a^{\varphi{(m)}} \equiv 1 \pmod{m}$ iff $gcd(a, m) = 1$. $\varphi{(m)}$ is the Euler totient function, that is, the quantity of numbers that are coprime with $m$. Coincidentally, if $m$ is prime, then $\varphi{(m)} = m - 1$

8. Originally Posted by Bacterius
Ironically, if $m$ is prime, then $\varphi{(m)} = m - 1$
I don't think "ironically" is the correct word here. It is coincidental that this is the case.

9. Effectively, just looked it up on the dictionary
It's quite hard to find the words sometimes ...
Forgive my english

10. Originally Posted by Bacterius
Effectively, just looked it up on the dictionary
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