PUMaC 2015 · 团队赛 · 第 15 题
PUMaC 2015 — Team Round — Problem 15
题目详情
- [ 12 ] Let S be the set of ordered integer pairs ( x, y ) such that 0 < x < y < 42 and there exists ∑ 6 6 2 2 some integer n such that x − y | n + 2015 . What is the sum x y ? i i ( x ,y ) ∈ S i i 5 5 5 5 5
解析
- [ 12 ] Let S be the set of ordered integer pairs ( x, y ) such that 0 < x < y < 42 and there exists ∑ 6 6 2 2 some integer n such that x − y | n + 2015 . What is the sum x y ? i i ( x ,y ) ∈ S i i 6 6 2 2 Solution: First, observe that if x and y are of the same parity, then 4 | x − y , but n +2015 ≡ 1 , 2 mod 4, which is not possible. WLOG, x is even and y is odd (we ignore the x < y constraint for now). 2 2 Let P be the set of primes equivalent to 3 mod 4. We claim that if some p ∈ P | x + y , 3 3 2 2 then p | gcd( x, y ). Indeed, if x, y exist with p - gcd( x, y ), we have from FLT and x ≡ − y p − 1 p − 1 p − 1 p − 1 2 k +1 2 2 mod p that 1 ≡ x ≡ ( − 1) y ≡ ( − 1) ≡ ( − 1) ≡ − 1 mod p , a contradiction. Thus, our claim is true. 2 2 If p ∈ P divides n + 2015 , it must divide gcd( n, 2015). The only p ∈ P that divides 2015 is 3 3 2 2 2 2 31, so p = 31. Then, 3 must divide exactly one of x, y , as otherwise, 3 | x − y | n + 2015 , but 3 ∈ P and 3 6 = 31, a contradiction. Similarly, 7 must divide exactly one of x, y . 3 6 6 2 2 2 2 Factoring, we have x − y = ( x + y )( x − y )( x + xy + y )( x − xy + y ). If x ≡ 2 mod 4, then 2 2 2 2 x + xy + y ≡ x − xy + y ≡ 3 mod 4. This means that both these expressions must have 2 2 2 2 some prime divisor p ∈ P , so 31 | x + xy + y , x − xy + y and 31 | 2 xy . If 31 divides x , then 3 2 31 divides x + xy and 31 divides y as well, and vice versa. Thus, 31 divides both x and y , so 2 2 2 2 2 4 6 6 2 2 31 | x + xy + y , x − xy + y and 31 | x − y | n + 2015 . However, this is impossible, as ( ) ( ) 2 n n 2 2 2 2 if 31 divides n + 2015 , 31 | n, 2015 and 31 | + 65 , but 31 - 65, so 31 - gcd , 65 , a 31 31 contradiction. Thus, x 6 ≡ 2 mod 4, so x ≡ 0 mod 4. This means one of x + y, x − y ≡ 3 mod 4, so 31 | ( x + y )( x − y ). We now count all pairs ( x, y ) satisfying 4 | x , 31 | ( x + y )( x − y ), and 21 | xy for x, y < 42. Two (uordered) pairs satisfy these conditions: (24 , 7) and (28 , 3). 6 6 6 6 Factoring 24 − 7 and 28 − 3 , we obtain 13 · 17 · 31 · 61 · 457 and 5 · 5 · 31 · 709 · 877. Note that each prime factor is equivalent to 1 mod 4 except for 31. For each prime factor p ∈ P , there 1 2 2 is a solution n modulo p such that n ≡ − 2015 mod p (as if r is a quadratic residue mod p p p , so is p − r ). By CRT, we can find some n such that n ≡ n mod p for all the prime factors p 2 2 2 2 6 6 2 2 p ∈ P and 31 | n , and it follows that p | n + 2015 and 31 | n + 2015 , so x − y | n + 2015 , 1 as desired. 6 6 2 2 Reintroducing the x < y condition, there exists some n such that x − y | n + 2015 for only the pairs (3 , 28) and (7 , 24), yielding a sum of 3 · 28 + 7 · 24 = 252 . Author: Bill Huang 5 5 5 5 5