HMMT 十一月 2022 · 团队赛 · 第 9 题
HMMT November 2022 — Team Round — Problem 9
题目详情
- [50] Call an ordered pair ( a, b ) of positive integers fantastic if and only if a, b ≤ 10 and gcd( a · n ! − 1 , a · ( n + 1)! + b ) > 1 for infinitely many positive integers n . Find the sum of a + b across all fantastic pairs ( a, b ).
解析
- [50] Call an ordered pair ( a, b ) of positive integers fantastic if and only if a, b ≤ 10 and gcd( a · n ! − 1 , a · ( n + 1)! + b ) > 1 for infinitely many positive integers n . Find the sum of a + b across all fantastic pairs ( a, b ). Proposed by: Pitchayut Saengrungkongka Answer: 5183 Solution: We first prove the following lemma, which will be useful later. n − 1 Lemma: Let p be a prime and 1 ≤ n ≤ p − 1 be an integer. Then, n !( p − 1 − n )! ≡ ( − 1) (mod p ). Proof. Write n !( p − n − 1)! = (1 · 2 · · · n )(( p − n − 1) · · · 2 · 1) p − n − 1 ≡ ( − 1) (1 · 2 · · · n )(( n + 1) · · · ( p − 2)( p − 1)) (mod p ) n = ( − 1) ( p − 1)! n − 1 ≡ ( − 1) (mod p ) (where we have used Wilson’s theorem). This implies the result. Now, we begin the solution. Suppose that a prime p divides both a · n ! − 1 and a · ( n + 1)! + b . Then, since − b ≡ a · ( n + 1)! ≡ ( n + 1) · ( a · n !) ≡ ( n + 1) (mod p ) , we get that p | n + b + 1. Since we must have n < p (or else p | n !), we get that, for large enough n , n = p − b − 1. However, by the lemma, b − 1 a ( − 1) ≡ a · b !( p − 1 − b )! = a · b ! n ! ≡ b ! (mod p ) . b − 1 This must hold for infinitely many p , so a = ( − 1) b !. This forces all fantastic pairs to be in form ((2 k − 1)! , 2 k − 1). Now, we prove that these pairs all work. Take n = p − 2 k for all large primes p . Then, we have a · n ! ≡ (2 k − 1)!( p − 2 k )! 2 k ≡ ( − 1) ≡ 1 (mod p ) a · ( n + 1)! ≡ ( n + 1) · ( a · n !) ≡ ( p − 2 k + 1) · 1 ≡ − (2 k − 1) (mod p ) , so p divides the gcd. The answer is (1 + 1) + (6 + 3) + (120 + 5) + (5040 + 7) = 5183.