How do you find the last digit of a number using Fermat's Little Theorem

Printable View

December 11th 2009, 01:45 PM
steph3824

How do you find the last digit of a number using Fermat's Little Theorem

For example, what is the last digit of 17^(3241)? It would help a ton if someone could show how to solve this using Fermat's Little Theorem. I have finals coming up and this was something I never quite understood
December 12th 2009, 03:18 AM
CaptainBlack

Quote:

Originally Posted by steph3824

For example, what is the last digit of 17^(3241)? It would help a ton if someone could show how to solve this using Fermat's Little Theorem. I have finals coming up and this was something I never quite understood

I'm not sure why one would need Fermat's little theorem for this since:

$17^3 \equiv 1 \text{ mod } 10$

and:

$17^{3241}=(17^3)^{1080}\times 17$

which immediately should tell you that:

$17^{3241}\equiv 7 \text{ mod } 10$

CB
December 12th 2009, 04:40 AM
alexmahone

Quote:

Originally Posted by CaptainBlack

I'm not sure why one would need Fermat's little theorem for this since:

$17^3 \equiv 1 \text{ mod } 10$

and:

$17^{3241}=(17^3)^{1080}\times 17$

which immediately should tell you that:

$17^{3241}\equiv 7 \text{ mod } 10$

CB

Incorrect!

$17^4 \equiv 1 (mod 10)$

$17^{3241}=(17^4)^{810}\times 17$

So $17^{3241}\equiv 7(mod 10)$
December 12th 2009, 11:24 AM
CaptainBlack

Quote:

Originally Posted by alexmahone

Incorrect!

$17^4 \equiv 1 (mod 10)$

$17^{3241}=(17^4)^{810}\times 17$

So $17^{3241}\equiv 7(mod 10)$

Oppsss.. arithmetic error (actually a transcription error with argument completed with the erroeous value)

CB
December 13th 2009, 05:52 AM
awkward

Quote:

Originally Posted by steph3824

For example, what is the last digit of 17^(3241)? It would help a ton if someone could show how to solve this using Fermat's Little Theorem. I have finals coming up and this was something I never quite understood

Here is a solution via Fermat's Last Theorem (although it's not necessarily the simplest):

By Fermat's Last Theorem, $17^4 \equiv 1 \mod 5$ ,
so since
$17^{3241} = (17^4)^{810} \cdot 17$ ,
$17^{3241} \equiv 1 \cdot 17 \equiv 2 \mod 5$ .

We also have $17 \equiv 1 \mod 2$ , so $17 ^ {3241} \equiv 1 \mod 2$ .

Since $17^{3241} \equiv 2 \mod 5$ and $17 ^ {3241} \equiv 1 \mod 2$ ,
$17^{3241} \equiv 7 \mod 10$ .
We could use the Chinese Remainder Theorem at the last step, but it seems like overkill here.