# Math Help - Fermat's little theorem

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

2. 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 ?

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

4. 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$

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

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 ?

5. Ah, thanks, it is better now. I'll be able to solve the rest now