## anonymous 4 years ago Fool's problem of the day, Find the remainder when $$44^8$$ is divided by $$119$$. PS:This problem is originated from one of the myininaya's reply at OS feedback chat.

1. RagingSquirrel

eh... i hate these

2. barrycarter

67 by brute force: http://fwd4.me/0lMq

3. anonymous

hehe

4. anonymous

For myin, the constraint is higher $$44^{86}$$ ;-)

5. anonymous

Its extremely easy. Here: 44^2 = 1936 = 32 mod 119 implies 44^4 = 32^2 = 1024 = 72 mod 119 implies 44^8 = 72^2 = 5184 = 67 mod 119

6. anonymous

Sure Aron, now try the one with higher constraints.

7. KingGeorge

Well, the second problem can be reduced to solving for x in$44^{10} x \equiv 1 \mod \; 119$using Euler's totient function. From there, we can find that$x=60$Unfortunately, I still need the help of Wolfram for that last step :(

8. anonymous

Okay,here it is : 86 = 2*43., 44 = 4*11 44^8 = 67 mod 119 implies 44^40 = 67^ 5 = 16 mod 119 implies 44^43 = 64*16= 72 mod 119 implies 44^86 = 72^2 = 5184 = 67 mod 119.Done!

9. anonymous

Aron, you are right apart from the fact the the remainder is not 67.

10. KingGeorge

Alternatively, we know that $44^{86}=44^{64}*44^{16}*44^4*44^2$and by computing successive squares of 44 modulo 119 we can also find that $44^{86} \equiv 60 \mod \: 119$

11. KingGeorge

This is the the same method Aron used for finding $44^8 \mod \: 119$

12. anonymous

That's right KIngGeorge, however it's extremely tedious when you don't have any electronic help.

13. KingGeorge

Is there a way to do it quickly without electronic help?

14. anonymous

There always is :)

15. anonymous

You can use Euler's & Fermat's Theorem!

16. KingGeorge

How so?

17. anonymous

@Fool I am sorry! I just checked the remainder to be 60.