HMMT 二月 2025 · 冲刺赛 · 第 27 题
HMMT February 2025 — Guts Round — Problem 27
题目详情
- [14] Compute the number of ordered pairs ( m, n ) of odd positive integers both less than 80 such that m m n n gcd(4 + 2 + 1 , 4 + 2 + 1) > 1 .
解析
- [14] Compute the number of ordered pairs ( m, n ) of odd positive integers both less than 80 such that m m n n gcd(4 + 2 + 1 , 4 + 2 + 1) > 1 . Proposed by: Pitchayut Saengrungkongka Answer: 820 Solution: First, we characterize all ordered pairs of general (not necessarily odd) positive integers m m n n ( m, n ) such that gcd(4 + 2 + 1 , 4 + 2 + 1) > 1. We claim that ( m, n ) works if and only if either • m and n are both even, or • ν ( m ) = ν ( n ). 3 3 m m n n Proof of necessity. Suppose that p is a prime that divides both 4 + 2 + 1 and 4 + 2 + 1. If p = 3, m and n must both be even. Henceforth assume that p ̸ = 3. Let d be the order of 2 modulo 3 m m p . Then, as p | 2 − 1, we find that d | 3 m . Furthermore, we cannot have p | 2 − 1. Otherwise, by lifting the exponent (and p ̸ = 3), 3 m m m m m ν (2 − 1) = ν (2 − 1) + ν (3) = ν (2 − 1) = ⇒ ν (4 + 2 + 1) = 0 . p p p p p The previous two results imply ν ( d ) = ν ( m ) + 1. Similarly, ν ( d ) = ν ( n ) + 1, so ν ( m ) = ν ( n ). 3 3 3 3 3 3 m m n n Proof of sufficiency. If m and n are both even, then 3 divides both 4 + 2 + 1 and 4 + 2 + 1. k k 3 3 m m n n If ν ( m ) = ν ( n ) = k , then we claim that 4 + 2 + 1 divides both 4 + 2 + 1 and 4 + 2 + 1. 3 3 k 2 2 ℓ ℓ 3 Indeed, note that as polynomials, x + x + 1 divides x + x + 1 when 3 ∤ ℓ . Plugging in x = 2 with k k ℓ = m/ 3 and ℓ = n/ 3 yields the desired result. Answer Extraction. We count pairs of odd integers ( m, n ) less than 80 with ν ( m ) = ν ( n ). Of all 3 3 integers in the set { 1 , 3 , 5 , . . . , 79 } , there are 27, 9, 3, and 1 of them that have ν equal to 0, 1, 2, and 3 2 2 2 2 3, respectively. Hence, the answer is 27 + 9 + 3 + 1 = 820 .