Raise to the seventh power, get factor (Posted on 2007-04-18)

	Submitted by K Sengupta
Rating: 3.3333 (3 votes)
Solution:	(Hide)
In terms of the explanation given below, all pairs (x,y) such that: (x Mod 343, y Mod 343)=(1, 18); (18, 1); (18, 324); (324, 18); (1, 324); (324, 1); (1,1); (18, 18); (324, 324) satisfy conditions of the problem. Therefore, there is an infinite number of solutions to the given problem It is trivial to observe that (x, y) = (1, 18); (18, 324); (1, 324) are three of the pairs which satsfy all the conditions of the problem. EXPLANATION: We find that (x + y)^7 - x^7 - y^7 = 7xy(x + y)(x^2 + xy + y^2)^2. Hence, we must determine x, y such that x^2 + xy + y^2 is divisible by 7^3. Now, we observe that: x^2 + xy + y^2 = (x^3 - y^3)/(x - y), so we are looking for pairs (x,y) with x^3 = y^3 (mod 7^3)....(i) We now observe in terms of Fermat-Euler theorem that : x^Phi(m)Mod m = 1 , where m is prime. But Phi(7^3) = 2*3*49, so x^3 Mod 343 = 1 if x = n^98. Similarly,from (i), it follows that y^3 Mod 343 = 1 Let n = 7r+p, where p =0,1,2,...,6 But p=0 gives n^98 Mod 343 = (7r)^98 Mod 343 =0, which violates the restrction that xy(x+y) is NOT a multiple of 7. Hence n = 1,2,3,4,5,6 Now, n^98 = (p+7r)^98 = p^98 + 343s, where s is an integer Accordingly, n^98 Mod 343 = p^98 Mod 343 Now, 2^10 Mod 343 = -5, giving 2^90 Mod 343 = -5^9 Mod343 Now, 5^4 Mod 343 = -61 Or, 5^8 Mod 343= 61^2 Mod 343 = 291 Or, -5^9 Mod 343 = -83 Hence, 2^98 Mod 343 = -83*256 Mod 343 = 18 Also, 4^98 Mod 343= 18^2 Mod 343 = 324 3^98 Mod 343 = 4^98 Mod 343 = 324 5^98 Mod 343 = 2^98 Mod 343 = 18 6^98 Mod 343 = -1^98 = 1 Thus, by (#) x Mod 343 = 1, 18, 324 as also, y Mod 343 = 1, 18, 324 Accordingly, all positive integer pairs (x,y) such that: (x Mod 343, y Mod 343) = (1, 18); (18, 1); (18, 324); (324, 18); (1, 324); (324, 1); (1,1); (18, 18); (324, 324) with x< y satisfy conditions of the problem.Therefore, there is an infinite number of solutions to the given problem. It is trivial to observe that (x, y) = (1, 18); (18, 324); (1, 324) are three of the pairs which satsfy all the conditions of the problem. ********************************************** Note: Other residue pairs (x Mod 343, y Mod 343) apart from the pairs given above which satisfy conditions of the problem does exist as has been rightly pointed out in the comments section. However, the residue pairs given above are sufficient to demonstrate that the given problem INDEED admits of an infinity of solutions.

	Subject	Author	Date
	Solution	Brian Smith	2007-04-21 16:09:38
	re(2): Hint	K Sengupta	2007-04-19 04:20:47
	Solution	Dej Mar	2007-04-19 02:52:21
	re: Hint	Dej Mar	2007-04-19 02:21:34
	Hint	K Sengupta	2007-04-19 01:21:01