# Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$. [duplicate]

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?

• To convert it into form $a$^$p$-$1$ -1 Sep 21, 2015 at 15:17

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$.
By FLT, $$5^{58} \equiv 1 \pmod{59}$$. Therefore, $$(5^{58})^2 \equiv 1\pmod{59}$$. We now need to compute $$5^3 \pmod{59}$$ which is a small computation that results in a remainder of $$7$$.