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.

Printable View

- February 23rd 2010, 01:26 PMtarheelbornFermat'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.

- February 23rd 2010, 01:45 PMcraig
Fermat's Little Theorem states that:

where p is a prime number.

Dividing both sides by a, we get:

Compare this to your question, what do you notice? - February 23rd 2010, 02:20 PMtarheelborn
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)?

- February 23rd 2010, 02:22 PMtarheelborn
Oops--duh--5^10 * 5^2 (mod 11) == 5^2 * 1(mod 11) == 3(mod 11). Right?

- February 23rd 2010, 07:20 PMBacterius
Hello, you want to solve this for :

By Fermat's Little Theorem, we are left with . Now, , and , so .

Basically, you want to simplify the difficult calculation until the remaining operations can be done mentally or easily on a calculator. It is up to you to decide whether can be calculated manually. - February 24th 2010, 12:14 PMcraig
- February 24th 2010, 07:02 PMBacteriusQuote:

Remember though that Fermat's little Theorem only works if p is a prime number.

**iff**. is the Euler totient function, that is, the quantity of numbers that are coprime with . Coincidentally, if is prime, then :D - February 24th 2010, 07:29 PMDrexel28
- February 24th 2010, 07:38 PMBacterius
Effectively, just looked it up on the dictionary (Yes)

It's quite hard to find the words sometimes ...

Forgive my english :( - February 24th 2010, 07:51 PMDrexel28
- February 24th 2010, 07:56 PMBacterius
:)