# Fermat's little theorem

• May 17th 2009, 01:35 AM
djsilva
Fermat's little theorem
Need help with computing the following by using Fermat's little theorem. I've been reading in advance and would like to wrap my head around this before the actual lesson, but I've found it trickier than expected. Any help is welcome! :)

10^117 (mod 7)
(17)^145 (mod 11)
3^302 (mod 5)
5^2003 (mod 13)
• May 17th 2009, 01:44 AM
Moo
Hello,

First, you can simplify :

$10^{117}\equiv 3^{117} (\bmod 7)$
Then Fermat's little theorem implies that $3^6\equiv (\bmod 7)$
Since $117=6\times 19+3$, you have :
$3^{117}=(3^6)^{19}\cdot 3^3 \equiv 1^{19}\cdot 27 (\bmod 7)$
And hence $10^{117}\equiv 6(\bmod 7)$

It's the same for the others. identity the number b such that $a^b\equiv 1(\bmod n)$, and then write the Euclidean division of the exponent by b.

For the second one, it simplifies also as $6^{145} (\bmod 11)$
Spoiler:
By Fermat's little theorem, we know that $6^{10}\equiv 1(\bmod 11)$
Since $145=14\times 10+5$, we have :
$6^{145}\equiv6^5 (\bmod 11)$

And then, it's pretty awful to calculate $6^5$, so note that $6^2=36\equiv 3(\bmod 11)$

So $6^5=6^2 \cdot 6\equiv 3^2 \cdot 6 (\bmod 11) \equiv 1 (\bmod 11)$

Does it look clear to you ?
• May 17th 2009, 06:10 AM
djsilva
Quote:

Originally Posted by Moo
Hello,

First, you can simplify :

$10^{117}\equiv 3^{117} (\bmod 7)$
Then Fermat's little theorem implies that $3^6\equiv (\bmod 7)$
Since $117=6\times 19+3$, you have :
$3^{117}=(3^6)^{19}\cdot 3^3 \equiv 1^{19}\cdot 27 (\bmod 7)$
And hence $10^{117}\equiv 6(\bmod 7)$

Does it look clear to you ?

Thanks for your help. I think I am understanding it now, but how did it become congruent to 1^19 . 27(mod 7)? And for the second question, how did 6^10 become congruent to 1(mod11)? Sorry, it's just that I am quite ill now, it usually takes me faster to grasp things. Thanks again :)
• May 17th 2009, 06:16 AM
Moo
Quote:

Originally Posted by djsilva
Thanks for your help. I think I am understanding it now, but how did it become congruent to 1^19 . 27(mod 7)?

Remember these properties :
$a\equiv b(\bmod n)\Rightarrow \begin{array}{ll} a^c\equiv b^c(\bmod n) \\ ac\equiv bc(\bmod n)\end{array}$

Because $3^6\equiv 1(\bmod 7)$, it follows that $(3^6)^{19}\equiv 1 (\bmod 7)$ (or $1^{19}$ if you need this step)
Then $3^{117}=(3^6)^{19} \cdot 3^3 \equiv 1\cdot 3^3 (\bmod 7)$
and since 3^3=27...

If you don't understand why $3^{117}=(3^6)^{19}\cdot 3^3$, I'll refer you to the properties of exponents : $a^{bc}=(a^b)^c=(a^c)^b$ and $a^{b+c}=a^b\cdot a^c$

Quote:

And for the second question, how did 6^10 become congruent to 1(mod11)?
This is Fermat's little theorem ^^

Quote:

Sorry, it's just that I am quite ill now, it usually takes me faster to grasp things. Thanks again :)
No problem. My explanations aren't the clearest possible either...

Can you try to do the last 2 ones ?
• May 17th 2009, 06:28 AM
djsilva
Ah, thanks, it is better now. I'll be able to solve the rest now :)