Check out some similar questions!

galactus · Jan 7, 2007, 06:14 AM

Here's a problem maybe you number theorists will like. Just an exercise in modular arithmetic. Think about Fermat's little theorem.

"Find the remainder when $5^{100}$ is divided by 7".

Yes, you could use a good calculator, but that's no fun.

Fianchetto · Jan 7, 2007, 06:00 PM

I can answer that questions in 6 tries or less:

"Is it 6?"
"Is it 5?"
"Is it 4?"
...
"Is it 1?" :)

Seriously, I got to brush up on that Fermat guy, and get back to you.
Thanks! :)
Fianchetto

galactus · Jan 9, 2007, 05:06 AM

We want $5^{100} \;\ mod \;\ 7$

Fermat's theorem states:

$a^{p-1}\equiv{1(mod \;\ p)}$

$5^{6}\equiv{1(mod \;\ 7)}$

Hence, $5^{100}=(5^{6})^{14}\cdot{5^{4}}\equiv{5^{4}}=625 \equiv{2 \;\ (mod \;\ 7)}$

Therefore, the remainder is 2.

asterisk_man · Jan 9, 2007, 07:17 AM

And I was just about to say that exact thing! ;)