Question

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.

Answer 1

eh... i hate these

Answer 2

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

Answer 3

hehe

Answer 4

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

Answer 5

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

Answer 6

Sure Aron, now try the one with higher constraints.

Answer 7

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 :(

Answer 8

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!

Answer 9

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

Answer 10

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\]

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

There always is :)

Answer 15

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

Answer 16

How so?

Answer 17

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