HMMT 二月 2020 · ALGNT 赛 · 第 7 题
HMMT February 2020 — ALGNT Round — Problem 7
题目详情
英文原题
- Find the sum of all positive integers n for which
15 · n ! + 12
2 n − 3
is an integer. 2
解析
英文解析
- Find the sum of all positive integers n for which
15 · n ! + 12
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
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 2
( ) ( )
p + 3 p − 3 p − 1
( − 1) · 15 · 1 · 2 · · · · · · · · ( p − 1) + 1 (mod p ) .n
2 2 2
By Wilson’s Theorem, ( p − 1)! ≡ − 1 (mod p ) , so the expression simplifies top − 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 numberswork aside from 7 (because 7 ≡ 3 (mod 4)) and the corresponding values of n are 10 and 77. The sumof the solutions is then 1 + 2 + 10 + 77 = 90. 2