1
$\begingroup$

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?

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .