HMMT 二月 2024 · ALGNT 赛 · 第 6 题

HMMT February 2024 — ALGNT Round — Problem 6

Compute the sum of all positive integers n such that 50 ≤ n ≤ 100 and 2 n + 3 does not divide 2 − 1 . 3 3 3

解析

Compute the sum of all positive integers n such that 50 ≤ n ≤ 100 and 2 n + 3 does not divide 2 − 1. Proposed by: Pitchayut Saengrungkongka Answer: 222 n ! Solution: We claim that if n ≥ 10, then 2 n + 3 - 2 − 1 if and only if both n + 1 and 2 n + 3 are prime. n ! If both n + 1 and 2 n + 3 are prime, then assume 2 n + 3 | 2 − 1. By Fermat Little Theorem, 2 n +2 2 2 n + 3 | 2 + 1. However, since n + 1 is prime, gcd(2 n + 2 , n !) = 2, so 2 n + 3 | 2 − 1 = 3, a contradiction. If 2 n + 3 is composite, then ϕ (2 n + 3) is even and is at most 2 n , so ϕ (2 n + 3) | n !, done. n ! If n + 1 is composite but 2 n + 3 is prime, then 2 n + 2 | n !, so 2 n + 3 | 2 − 1. The prime numbers between 50 and 100 are 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97. If one of these is n + 1, then the only numbers that make 2 n + 3 prime are 53 , 83 , and 89, making n one of 52, 82, and 88. These sum to 222 . 3 3 3