All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A 2011 Problem (Posted on 2007-03-17)
Determine the remainder when (201156 + 34)28 is divided by 111.

Can you do this in a short time using pen and paper, and eventually a hand calculator, but no computer programs?

 Submitted by K Sengupta No Rating Solution: (Hide) 111 = 3*37. Now, 2011= -1 (mod 3) and, so 2011^56 = (-1)^56 = 1 (mod 3) Accordingly, 2011^56 + 34 = -1 (mod 3), giving: (2011^56 + 34)^28 = (-1)^28 (mod 3) = 1 (mod 3) Now, 2011 = 13 (mod 37); so that: 2011^56 = 13^56 (mod 37) 13^2 = 21(mod 37); 13^3 = 14 (mod 37); 13^4 = 21^2 (mod 37) = -3 (mod 37) 13^7 = (14)*(-3) (mod 37) = -5 (mod 37) 13^14 = 25 (mod 37) 13^28 = 25^2 (mod 37) = -4 (mod 37) 13^56 = 16 (mod 37) So, (2011^56 + 34)^28 = (16+34)^28 (mod 37) = 50^28 (mod 37) = 13^28( mod 37) = -4 (mod 37) = 33 (mod 37) Accordingly, (2011^56 + 34)^28 = 1 (mod 3) = 33 (mod 37) We observe that 3 and 37 are prime to each other. Now the only number less than 111 that yields the respective remainders 1 and 33 when divided separately by 3 and 37 is 70. Consequently, the required remainder is 70. NOTE: This problem was inspired by the topic Remainder when Dividing Large Numbers inclusive of the Math Forum.

 Subject Author Date solution Charlie 2007-03-17 14:37:35 Silly questions get silly answers Ady TZIDON 2007-03-17 13:44:14 It remains to be said.... Dej Mar 2007-03-17 12:28:21

 Search: Search body:
Forums (0)