HMMT 十一月 2021 · 团队赛 · 第 9 题

HMMT November 2021 — Team Round — Problem 9

[55] Let N be the smallest positive integer for which ∑ 2 d x + x + 1 divides 166 − x . d | N, d> 0 Find the remainder when N is divided by 1000.

解析

[55] Let N be the smallest positive integer for which ∑ 2 d x + x + 1 divides 166 − x . d | N, d> 0 Find the remainder when N is divided by 1000. Proposed by: Joseph Heerens Answer: 672 2 πi/ 3 Solution: Let ω = e . The condition is equivalent to ∑ d 166 = ω . d | N,d> 0 d Let’s write N = 3 n where n is not divisible by 3. If all primes dividing n are 1 mod 3, then N has a ∑ d positive number of factors that are 1 mod 3 and none that are 2 mod 3, so ω has nonzero d | N,d> 0 imaginary part. Therefore n is divisible by some prime that is 2 mod 3. In this case, the divisors of n are equally likely to be 1 or 2 mod 3, so the sum is 1 2 d − 1 − τ ( n ) + dτ ( n ) = τ ( n ) . 2 2 2 Now, 2 · 166 = 2 · 83 and 83 is prime, so we must either have d = 42, which forces τ ( n ) = 4, or d = 1, 42 3 which forces τ ( n ) = 332. The first cases yields a lower value of N , namely 3 2 . 5 Now let’s try to compute this mod 1000. This is clearly divisible by 8. Modulo 125, 3 = 243 ≡ − 7, so 20 40 42 3 3 ≡ 2401 ≡ 26 and 3 ≡ 676 ≡ 51. Therefore 3 2 ≡ 72 · 51 = 3672 mod 125. Since 672 is divisible by 8, this is our answer.