Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$.
Fermat's little theorem states that if $p$ is prime and $\operatorname{gcd}(a,p)=1$,then $a^{p-1} -1$ is a multiple of $p$.
For example, $p=5,a=3$. From the theorem, $3^5-1 -1$ is a multiple of $5$ i.e $80$ is a multiple of $5$.
Similarly, I need to find the remainder when $5^{119}$ is divided by $59$.
My approach:
Using theorem I solve:
$5^{119-1} -1=5^{118} – 1 \Rightarrow 5^{118}=59k+1$, where $k$ is a natural number.
How do I proceed?
Best Answer
According to Fermat's theorem $a^{p-1}\equiv 1 \pmod p$. Here $p=59$ hence $a^{58} \equiv 1 \pmod {59}$.
Now $a^{119}=a^{2\times58+3}=a^{58\times2}a^3\equiv 1\times a^3 \pmod {59}$
In your case $a=5$, therefore $5^{119}\equiv 5^3\equiv 7 \pmod {59}$
So the answer is $7$.