HMMT 二月 2025 · 团队赛 · 第 10 题
HMMT February 2025 — Team Round — Problem 10
题目详情
- [60] Determine, with proof, all possible values of gcd( a + b + c , abc ) across all triples of positive integers ( a, b, c ).
解析
- [60] Determine, with proof, all possible values of gcd( a + b + c , abc ) across all triples of positive integers ( a, b, c ). Proposed by: Henrick Rabinovitz Answer: All positive integers n such that ν ( n ) ̸ = 1 for all prime p ≡ 3 (mod 4) p Solution: First, we show that no other n work. If there does exist prime p ≡ 3 (mod 4) such that 2 2 2 2 2 ν ( n ) = 1, then p | abc ; without loss of generality, assume p divides a . Then, p | a and p | a + b + c , p 2 2 2 2 so p | b + c . Since p is 3 modulo 4, − 1 is not a quadratic residue modulo p , so b ≡ − c (mod p ) 2 only has the trivial solution ( b, c ) = 0. Therefore p | b and p | c , so p | n . This contradicts ν ( n ) = 1, p so no solutions outside of the claimed solution set exist. Now, we give the construction. Let n be in the claimed solution set. We proceed in two steps. ν ( n )+1 p Step 1 (Local step). For each prime p dividing n , we will construct a , b , and c modulo p such 2 2 2 that ν (gcd( a + b + c , abc )) = ν ( n ). p p We have a couple cases. k k k +1 • If ν ( n ) = 2 k for some positive integer k , pick a = p , b = p , and c = p for p ̸ = 2 and pick p k a = b = c = p for p = 2. • If p ̸ ≡ 3 (mod 4) and ν ( n ) = 2 k + 1 for some nonnegative integer k , then by Fermat’s p 2 2 k Christmas theorem, there are positive integers x and y for which x + y = p . Then pick a = xp , k k +1 b = yp , and c = p . • If p ≡ 3 (mod 4) and ν ( n ) = 2 k + 1 for some nonnegative integer k , then k ≥ 1 by p 2 2 assumption. We let x and y be positive integers for which ν ( x + y + 1) = 1. (This is fairly p 2 2 standard. To briefly recall the proof, note that x and y satisfying x + 1 ≡ − y (mod p ) exist because some 2 2 2 quadratic residue must be adjacent to a nonquadratic residue, and forcing x + 1 ̸ ≡ − y (mod p ) can be done by k k k adding appropriate multiples of p to x or y .) Then, pick a = xp , b = yp , and c = p . ν ( n )+1 p Step 2 (Global step). Given solutions ( a , b , c ) modulo p for each prime p | n , we construct p p p a working solution ( a, b, c ) over positive integers. By Chinese Remainder Theorem, we can pick positive integers a , b , and c such that for all prime p | n , ν ( n )+1 p ( a, b, c ) ≡ ( a , b , c ) (mod p ). Now, we need to modify this construction to ensure that no p p p 2 2 2 other primes divide gcd( a + b + c , abc ). For every prime p | c with p ∤ n , we modify a and b (by adding additional congruence relations) so that 2 2 2 2 2 p does not divide a + b . Then, p does not divide gcd( a + b + c , abc ) for any prime p such that p | c and p ∤ n . Let Y ν ( n )+1 p N = p , p | cn S = { primes p such that p | ab but p ∤ cn } , Y φ ( N ) P = p ≡ 1 (mod N ) . p ∈ S In particular, we have only fixed residues of a, b, c modulo N at this point. Now, let a = aP and 1 b = bP . This keeps all of our mod N conditions. We now claim that ( a , b , c ) works. To prove this, 1 1 1 fix a prime p , and note that ′ ′ 2 2 • if p divides cn , then since a ≡ a (mod N ) and b ≡ b (mod N ), we have ν (gcd( a + b + p 1 1 2 c , a b c )) = ν ( n ) from our construction of ( a, b, c ). 1 1 p 2 2 2 2 2 2 • if p ∈ S , then we note that p divides a + b , but not c , so p does not divide a + b + c . 1 1 1 1 • if p / ∈ S and p ∤ cn , then p does not divide a b c . 1 1 This concludes the proof.