HMMT 二月 2024 · 冲刺赛 · 第 18 题

HMMT February 2024 — Guts Round — Problem 18

[11] An ordered pair ( a, b ) of positive integers is called spicy if gcd( a + b, ab + 1) = 1 . Compute the probability that both (99 , n ) and (101 , n ) are spicy when n is chosen from { 1 , 2 , . . . , 2024! } uniformly at random.

解析

[11] An ordered pair ( a, b ) of positive integers is called spicy if gcd( a + b, ab + 1) = 1 . Compute the probability that both (99 , n ) and (101 , n ) are spicy when n is chosen from { 1 , 2 , . . . , 2024! } uniformly at random. Proposed by: Pitchayut Saengrungkongka 96 Answer: 595 Solution: We claim that ( a, b ) is spicy if and only if both gcd( a +1 , b − 1) = 1 and gcd( a − 1 , b +1) = 1 . To prove the claim, we note that 2 gcd( a + b, ab + 1) = gcd( a + b, b ( − b ) + 1) = gcd( a + b, b − 1) . Hence, we have 2 gcd( a + b, ab + 1) = 1 ⇐⇒ gcd( a + b, b − 1) = 1 ⇐⇒ gcd( a + b, b − 1) = 1 and gcd( a + b, b + 1) = 1 ⇐⇒ gcd( a + 1 , b − 1) = 1 and gcd( a − 1 , b + 1) = 1 , proving the claim. Thus, n works if and only if all following four conditions hold: • gcd( n + 1 , 98) = 1 , or equivalently, n is neither − 1 (mod 2) nor − 1 (mod 7) ; • gcd( n − 1 , 100) = 1 , or equivalently, n is neither 1 (mod 2) nor 1 (mod 5) ; • gcd( n + 1 , 100) = 1 , or equivalently, n is neither − 1 (mod 2) nor − 1 (mod 5) ; and • gcd( n − 1 , 102) = 1 , or equivalently, n is neither 1 (mod 2) , 1 (mod 3) , nor 1 (mod 17) . Thus, there are 1 , 2 , 3 , 6 , 17 possible residues modulo 2 , 3 , 5 , 7 , and 17 , respectively. The residues are 1 2 3 6 16 96 uniformly distributed within { 1 , 2 , . . . , 2024! } . Hence, the answer is · · · · = . 2 3 5 7 17 595