elementary number theory - Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$?

How to find the remainder using Fermat's little theorem?

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?

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