Home > Numbers
A 2011 Problem (Posted on 2007-03-17 )

Determine the remainder when (2011^{56} + 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.

Comments: (
You must be logged in to post comments. )

Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox: