HMMT 二月 2020 · ALGNT 赛 · 第 7 题

HMMT February 2020 — ALGNT Round — Problem 7

Find the sum of all positive integers n for which 2 15 · n ! + 1 2 n − 3 is an integer. 2

解析

Find the sum of all positive integers n for which 2 15 · n ! + 1 2 n − 3 is an integer. Proposed by: Andrew Gu Answer: 90 Solution: It is clear that n = 1 and n = 2 work so assume that n > 2. If 2 n − 3 is composite then 2 n − 3 2 its smallest prime factor is at most < n so will be coprime to 15 · n ! + 1. Therefore assume that 2 2 n − 3 = p is prime. We can rewrite the numerator as ( ) ( ) p + 3 p − 3 p − 1 n ( − 1) · 15 · 1 · 2 · · · · · · · · ( p − 1) + 1 (mod p ) . 2 2 2 By Wilson’s Theorem, ( p − 1)! ≡ − 1 (mod p ) , so the expression simplifies to p − 3 p − 1 p + 1 p + 3 135 n +1 n +1 ( − 1) · 15 · · · · + 1 ≡ ( − 1) · + 1 (mod p ) . 2 2 2 2 16 If p ≡ 3 (mod 4), then we have 135 + 16 151 ≡ ≡ 0 (mod p ) . 16 16 If p ≡ 1 (mod 4), then we have 135 − 16 119 ≡ ≡ 0 (mod p ) . 16 16 So p must be a prime divisor of 151 or 119, which means that p ∈ { 7 , 17 , 151 } . All of these numbers work aside from 7 (because 7 ≡ 3 (mod 4)) and the corresponding values of n are 10 and 77. The sum of the solutions is then 1 + 2 + 10 + 77 = 90. 2