A 2006 Problem (Posted on 2006-07-27)

	Submitted by K Sengupta
Rating: 3.3333 (3 votes)
Solution:	(Hide)
The required remainder is 145. EXPLANATION: Both 61 and 17 are prime numbers and since (17,61)=1, by Fermat’s Little Theorem, 61^16=1 (Mod 17) giving, 61^2000=1 (Mod 17). We observe that, 61=10 (Mod 17), so that 61^6=(-7)^6 (Mod 17)= 7^6 (Mod 17). Now, 7^2= -2 (Mod 17); so that 7^6= - 8 (Mod 17). Hence, 61^6= -8 (Mod 17), giving 61^2006= (61^2000)(61^6)= 1*(-8) (Mod 17)= - 8 Mod(17))= 9 Mod(17). Again, 61^58 = 1(Mod 59), giving, 61^1972 = 1(Mod 59).Now, 61=2(Mod 59), so that, 61^34 = 2^34(Mod 59).Now, 2^6 = 5 (Mod 59); while 5^3=7 (Mod 59), giving 5^5 = 175 (Mod 59)= 57 (Mod 59), so that, 2^30 = 57 (Mod 59)= (-2)(Mod 59).Therefore, 2^34 = (-2)(2^4)= -32 (Mod 59)= 27 (Mod 59).Consequently, 2^2006 = (2^1972)(2^34)=1*27(Mod 59)= 27(Mod 59), so that, 61^2006 = 27(Mod 59) Since, 61 is odd, it follows that 61^2006 is also odd. odd.Accordingly: 61^2006 = 27 Mod (59) = 9(Mod 17)= 1 Mod(2).---------(#) Let, us denote 61^2006 by x, and the required remainder by r. So, x-r is divisible by 2006 = 2*17*59; and since 2,17 and 19 are pairwise coprime, it follows that (x-r) is divisible by each of 2,17 and 59. From the first congruence, we obtain, x = 59*L + 27 = 9(Mod 17) or, r = 9 (mod 17) giving, 59L + 18 = 0 (Mod 17); or, 8L + 1 = 0 (Mod 17); giving L = 2 (Mod 17) or, L = 17*M + 2, for some M. Consequently, r = 59(17*M + 2)+ 27 = 1003*M + 145. For M=0, we obtain r = 145. For, M greater than or equal to 2,we obtain r > = 2151 > 2006, which is not feasible. For M=1, we obtain r = 1148, which is even and thus contradicts (#) Consequently, it follows that the required remainder must be 145. -------------------------------------------------------------------------------- Also refer to Nick Hobson's methodology given in this location.

	Subject	Author	Date
	Another approach	Nick Hobson	2006-08-30 20:36:58
	re: Howto	Federico Kereki	2006-07-29 11:49:36
	re: CORRECTION	Federico Kereki	2006-07-29 11:48:22
	CORRECTION	Ady TZIDON	2006-07-29 01:56:19
	re: A solution	Richard	2006-07-28 00:14:36
	A solution	Dej Mar	2006-07-27 17:36:48
	Howto	e.g.	2006-07-27 16:05:50
	Advice (Read only if you are really stuck)	Richard	2006-07-27 13:54:30