A 2011 Problem (Posted on 2007-03-17)

	Submitted by K Sengupta
Rating: 5.0000 (1 votes)
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