A Remainder Problem (Posted on 2006-08-08)

	Submitted by K Sengupta
Rating: 3.5000 (2 votes)
Solution:	(Hide)
FIRST PART: At the outset, we know that: 3^4 = 1 (Mod 20); giving, 3^(4k+m) = 3^m (Mod 20) for m=0,1,2,3 where 3^m = j (Mod 20) having, (m=0,j=1),(m=1,j=3), (m=2, j=9),(m=3, j=7), (m=4,j=1). Clearly, for m =0 or 2, the last digit of (4k+m) is odd, while the exponent of 3 is even. This contravenes the provisions of the problem. Consequently, x must possess the form (4k+1) or (4k+3) --------------------(#) Again 3^10 = 9^5 = (10-1)^5 = 10^5 - 5*(10^4)+10*(10^3)-5*(10^2) +5*10 -1 = 49 (Mod 100); giving, 3^20 = 2401 (Mod 100) = 1 (Mod 100) so that, 3^(20*m + j) = 3^j(Mod 100), whenever j=0,1,2,……………,19-----..(##) From (#) and (##) having regard to the coincidence of the exponent of 3 and the remainder upon division by 100, we observe that only j = 7 and 13 are valid options. Now, 3^4 = 81 (Mod 100) ; 3^5 = 43 (Mod 100); 3^6 = 29 Mod (100);3^7 = 87(Mod 100) Hence, 3^(20k + 7) = 87 Mod (100) (from (##)), since 87 also possess the form 20k+7, it follows that x=87 is a solution. 3^6 = 29 (Mod 100), so that, 3^12 = 41 (Mod 100), giving, 3^13 = 23 (Mod 100) Consequently, 3^(20*k + 13) = 23 (Mod 100). However, 23 does not possess the form 20*k + 13. This is a contradiction. Therefore, x =87 constitutes the only solution to the given problem. SECOND PART: At the outset, 2^0 = 1= 1 (Mod 100), where the power of 2 and the remainder are not coincident, and therefore a contradiction. Since 2^4=16, and any given power of 16 must possess 6 as the last digit, we obtain: 2^(4*k+ m) = 2^m (Mod 10) for m=1,2,3,4 with 2^m=j (Mod 10) having, (m=1, j=2),(m=2,j=4),(m=3,j=8) and (m=4, j=6) . Clearly, the conditions of the problem will only be satisfied for even m, so that m=2,4……………………………(#) Now, 2^(20) = 16^5. Now, 16^2 = 56 (Mod 100), giving 16^4 = 56^2 (Mod 100) = 36 (Mod 100); so that, 16^5= 576 (Mod 100) = 76 (Mod 100). Since 76^k = 76 (Mod 100), for any given interger k: Also, 2^(20k + 1) = 52 (Mod 100);2^(20k +2) = 4(Mod 100), and so on. we obtain, 2^(20*k + m) = 2^m (Mod 100), for m = 2,3, ------,19,20 and 2^(20k +1) =52 . (##) Having regard to (#) and (##), we observe that only m=14 and 16 are valid options. 2^6 =64, or, 2^12 = 64^2 = 96 (Mod 100) so that 2^14 = 84 (Mod 100), giving: 2^(20*k+14) = 84 (Mod 100). But, 84 possesses the form 20*k+4, and this is a contradiction. Since, 2^14 = 84 (Mod 100), it follows that, 2^16 = 36 (Mod 100). Hence: 2^(20*k+16) = 36 (Mod 100). Since, 36 possesses the form 20*k + 16, it follows that y =36 constitutes the only possible solution to the problem under reference.. ------------------------------------------------------------------------------------ A computer assisted solution to a more general version of this problem as submitted by Richard is given in this location.

	Subject	Author	Date
	A different (wrong) read on the problem, but interesting	Mike	2006-08-12 22:05:19
	1 to 9 to the x	Richard	2006-08-09 21:01:36
	solution	Dej Mar	2006-08-09 03:20:51
	Solution for both x and y	nirmal	2006-08-08 17:17:01
	Not Any Real Spoiler	Richard	2006-08-08 13:44:13