HMMT 二月 2026 · 冲刺赛 · 第 21 题
HMMT February 2026 — Guts Round — Problem 21
题目详情
- [12] Compute the largest possible value of (( ) ( ) ) n n gcd − 1 , − 1 3 4 as n ranges through all positive integers greater than 3 .
解析
- [12] Compute the largest possible value of (( ) ( ) ) n n gcd − 1 , − 1 3 4 as n ranges through all positive integers greater than 3 . Proposed by: Pitchayut Saengrungkongka Answer: 102 Solution: We first prove the following claim. ©2026 HMMT Claim 1. Let p be an integer-coefficient polynomial and d be a positive integer, and define the function ′ f ( n ) = p ( n ) /d . Let n and n be integers, q be a prime, and d be the largest power of q that divides 1 2 ′ d . if n ≡ n (mod qd ) , then f ( n ) ≡ f ( n ) (mod q ) . 1 2 1 2 ′ ′ ′ Proof. Since qd | n − n , we know qd | p ( n ) − p ( n ) . Since d/d is not divisible by q , we conclude 2 1 2 1 ∣ ∣ ′ ∣ ∣ d 1 ′ ∣ ∣ qd ( p ( n ) − p ( n )) = ⇒ q ( p ( n ) − p ( n )) = f ( n ) − f ( n ) . 2 1 2 1 2 1 ∣ ∣ d d ( ) ( ) n n In particular, both f ( n ) = − 1 and f ( n ) = − 1 can be written in this form p ( n ) /d with d = 6 3 4 3 4 and d = 24 , respectively. With that in mind, we note that a gcd of 102 is achievable by n = 823 (or 4 2 more generally, n ≡ 823 (mod 2448) where 2448 = 2 · 3 · 17 ). This works because ( ) ( ) 7 7 3 • the gcd is divisible by 2 since n ≡ 7 (mod 2 · 2 ) and 2 divides both − 1 = 34 and − 1 = 34 , 3 4 ( ) ( ) 4 4 1 • the gcd is divisible by 3 since n ≡ 4 (mod 3 · 3 ) and 3 divides both − 1 = 3 and − 1 = 0 , 3 4 and ( ) 7 0 • the gcd is divisible by 17 since n ≡ 7 (mod 17 · 17 ) and 17 divides both − 1 = 34 and 3 ( ) 7 − 1 = 34 . 4 (The exact value of 823 need not be calculated, as it exists by Chinese Remainder Theorem.) (( ) ( ) ) n n We now prove that the gcd has to be at most 102 . Let d = gcd − 1 , − 1 . We first show that 3 4 d divides 204 . To do this, note that d divides (( ) ) (( ) ) n n ( n − 3) − 1 − 4 · − 1 3 4 ( ) ( ) n ( n − 1)( n − 2) n ( n − 1)( n − 2)( n − 3) = ( n − 3) − 1 − 4 · − 1 6 24 = ( n − 3) − 4 = n − 7 . Since d also divides (( ) ) n 2 6 − 1 = n ( n − 1)( n − 2) − 6 = ( n − 7)( n + 4 n ) + 204 , 3 we get that d | 204 . It remains to show that d cannot be divisible by 4 . Assume for sake of contradiction that 4 divides ( ) ( ) ( ) n n n both − 1 and − 1 . Since 4 divides − 1 , we have that 3 4 3 n ( n − 1)( n − 2) ≡ 6 (mod 16) , ( ) n and since 4 divides − 1 , we have that 4 n ( n − 1)( n − 2)( n − 3) ≡ 24 (mod 64) . In particular, ν ( n ( n − 1)( n − 2)) = 1 and ν ( n ( n − 1)( n − 2)( n − 3)) = 3 , so ν ( n − 3) = 2 , which 2 2 2 means n ≡ 7 (mod 8) . However, this means n ( n − 1)( n − 2) ≡ 7 · (7 − 1) · (7 − 2) ≡ 2 (mod 8) , contradicting n ( n − 1)( n − 2) ≡ 6 (mod 16) . Hence, 4 ∤ d , As d | 204 , we conclude d ≤ 102 . ©2026 HMMT