HMMT 十一月 2022 · 团队赛 · 第 7 题
HMMT November 2022 — Team Round — Problem 7
题目详情
- [45] Compute the number of ordered pairs of positive integers ( a, b ) satisfying the equation 2 gcd( a, b ) · a + b = 10000 .
解析
- [45] Compute the number of ordered pairs of positive integers ( a, b ) satisfying the equation 2 gcd( a, b ) · a + b = 10000 . Proposed by: Vidur Jasuja Answer: 99 ′ ′ 2 ′ ′ 2 2 Solution 1: Let gcd( a, b ) = d, a = da , b = db . Then, d ( a + b ) = 100 . Consider each divisor d of 2 100 ′ ′ 2 100 . Then, we need to find the number of solutions in coprime integers to a + b = . Note that 2 d 2 100 100 ′ every b < 100 /d coprime to satisfies this equation, which is equivalent to being coprime to , so 2 d d 100 then there are φ choices for each d , except for d = 100, which would count the solution (0 , 100). d P 100 Then we just need φ − 1 = 100 − 1 = 99 . d | n d Solution 2: Note that b must be at most 99 in order for a to be positive. Now we claim that each choice of b ∈ { 1 , 2 , . . . , 99 } corresponds to exactly one value of a that satisfies the equation. To see why this is true, we rewrite the formula as gcd( a, b ) · a = (100 − b )(100 + b ) . k For any prime p , let v ( n ) be the largest integer k such that p | n . We wish to show that once we fix b , p the value v ( a ) is uniquely determined for all p (which will give us a unique solution for a ). Applying p v to both sides of the equation gives us p min( v ( b ) , v ( a )) + v ( a ) = v (100 − b ) + v (100 + b ) . p p p p p We immediately see that there is at most one solution for v ( a ) since the left-hand side increases with p v ( a ). Further, as we increment v ( a ), the left-hand side takes on all even numbers up to 2 v ( b ), p p p and then all integers larger than 2 v ( b ). So to show that a solution exists, we need to prove that the p right-hand side is always either even or at least 2 v ( b ). p If v ( b ) ̸ = v (100), then v (100 − b ) = v (100 + b ) = min( v (100) , v ( b )). In this case, v (100 − p p p p p p p b ) + v (100 + b ) is clearly even. Otherwise, assume v ( b ) = v (100). Then v (100 − b ) ≥ v ( b ) and p p p p p v (100 + b ) ≥ v ( b ), so v (100 − b ) + v (100 + b ) ≥ 2 v ( b ) as desired. Thus, there is always a unique p p p p p solution for v ( a ). Once we fix 1 ≤ b ≤ 99, the value of a is uniquely determined, so the answer is 99. p