4
$\begingroup$

Find the remainder when $787^{777}$ is divided by $100$?

MyApproach

$787^{20\times38+17}$=$787^{17}$=I will get the last digit of remainder as 7 but how to calculate tens digit in this question fast using this approach only.

Similarly,Find the remainder when $948^{728}$ is divided by $100$.

On solving I get $948^8$=I will get the last digit of remainder as 7 but how to calculate tens digit in this question fast using this approach only.

Again here how to calculate the other digits fast.

$\endgroup$
  • $\begingroup$ The answer depends on last two digits of $87^{777}$ $\endgroup$ – Pratyush Nov 3 '15 at 9:48
  • $\begingroup$ @Pratyush Yes but calculating it is even longer. $\endgroup$ – justin takro Nov 3 '15 at 9:50
  • $\begingroup$ ya right i am looking for a shorter one. $\endgroup$ – Pratyush Nov 3 '15 at 9:52
  • $\begingroup$ I am disappointed to see that all the answers (except the one by Lab Bhattacharjee) concentrate on rigorous computation rather than finding a smart idea to solve this. $\endgroup$ – I am Back Jul 2 '17 at 3:29
2
$\begingroup$

$787\equiv-13\pmod{100}$

$\implies787^{777}\equiv(-13)^{777}\equiv-13^{777}$

Now $13^2=170-1\implies13^{777}=13(-1+170)^{388}$

and $(-1+170)^{388}\equiv(-1)^{388}+\binom{388}1(-1)^{387}170\pmod{100}$ $\equiv1-388\cdot170$

Again as $388\cdot17\equiv6\pmod{10},388\cdot170\equiv60\pmod{100}$

Hope you can take it from here!

$\endgroup$
0
$\begingroup$

Hint

$787^3 \equiv 03\pmod {100}$ and $3^{20} \equiv 01 \pmod {100}$

Now the problem becomes much simpler. The last two digits of $787^{780}$ are $01$. You can now easily work backwards.

Other Problem

You can tackle it similarly by observing

$948^2 \equiv 04\pmod {100}$ and $4^{16} \equiv 04 \pmod {100}$

(You are not going to be lucky because with an even number, you will never get a $01$)

Edit - Alternately for first problem

You can use Fermat's little theorem, knowing $\phi(100) = 40$.

So any number, relatively prime with $100$, raised to $40$ will give $01$ and hence the last two digits of $787^{780}$ are $01$

$\endgroup$
  • $\begingroup$ How u did this.I understood that approach only which I mentioned. $\endgroup$ – justin takro Nov 3 '15 at 9:50
  • $\begingroup$ $3^{20}\equiv1\mod 100$ as $\lambda(100)=20$, which I think you tried to used. $\endgroup$ – Element118 Nov 3 '15 at 9:51
  • $\begingroup$ 787, I just hand-calculated -- you need only last 2 digits. On $3^{20}$, I knew it, just like $7^4$. See Subhadeep Dey's comment below $\endgroup$ – Shailesh Nov 3 '15 at 9:51
  • 1
    $\begingroup$ @justintakro, do you know congruence theory? $787\equiv 87\equiv-13\pmod {100}$ $\endgroup$ – user249332 Nov 3 '15 at 9:51
  • $\begingroup$ Any odd number raised to relative prime to 100 or 1000 or 4 has its last digit 1. Then find out last 2 digits and you will get the remainder. $\endgroup$ – Archis Welankar Nov 3 '15 at 9:53
0
$\begingroup$

$$787^{777}\equiv x(mod~100)$$ and you need to find $x$. Let's go this way

In every step we will take last two digits only, as the remainder when divided by $100$ depends upon last $2$ digits only. So $$787^{777}=(787^3)^{259}$$Now you don't have to do complete multiplication , just find last two digits of $87*87$ and multiply it by $87$ and again left all the digits except last two. Do, it for every next case$$787^{777}\equiv(787^3)^{259}\equiv(03)^{259}\equiv(03^7)^{37}\equiv(87)^{37}\equiv(87^3)^{12}\cdot87\equiv(03)^{12}\cdot87\equiv(3^6\cdot3^6)\cdot87\equiv(729\cdot729)\cdot87\equiv(29\cdot29)\cdot87\equiv41\cdot87\equiv3567\equiv67(mod~100)$$

So the answer is $67$ when $787^{777}$ is divided by $100$

For your second question, same approach works and solution comes out to be like this $$948^{728}\equiv(48^2)^{364}\equiv(04)^{364}\equiv(04^7)^{52}\equiv(2^{14})^{52}\equiv(96)^{52}\equiv(96^2)^{26}\equiv(16)^{26}\equiv(16^2)^{13}\equiv(56)^{13}\equiv(56^2)^6\cdot56\equiv(36)^6\cdot56\equiv(36^2)^3\cdot56\equiv(96)^3\cdot56\equiv(96)^2\cdot96\cdot56\equiv16\cdot96\cdot56\equiv36\cdot56\equiv2016\equiv16(mod~100)$$

So the answer is $16$ is the remainder whn $948^{728}$ is divided by $100$

From this method, I learnt how to calculate last two (or more) digits of a number because it is easily understandable.

$\endgroup$
-1
$\begingroup$

We have $\pmod{100}$

$$787^{777}\equiv 87^{777}$$

And we have the following factorisations

$$87=3\times 29$$ $$777=3\times 7\times 37$$

$$87^3=658503\equiv 3\pmod{100}$$

And so

$$787^{777}\equiv 3^{7\times 37}\pmod{100}$$

Now we have $3^7=2187\equiv 87$ and so

$$787^{777}\equiv (3\times 29)^{37}\pmod{100}$$

So we're now left with $3^{37}$ and $29^{37}$ $\pmod{100}$.

A direct computation shows that $3^{15}=14348907\equiv 7\pmod{100}$ and $3^7=2187\equiv 87$ so

$$3^{37}\equiv 7\times 7\times 87=4263\equiv 63\pmod{100}$$

Another direct (and painful) computation shows that $29^7=17249876309\equiv 9$ and $29^{10}=420707233300201\equiv 1$ and so

$$29^{37}\equiv 9\pmod{100}$$

And now putting the two results together

$$787^{777}\equiv 9\times 63=567\equiv 67\pmod{100}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.