返回题库

HMMT 二月 2020 · ALGNT 赛 · 第 7 题

HMMT February 2020 — ALGNT Round — Problem 7

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

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

英文解析

  1. 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