HMMT 二月 2016 · 冲刺赛 · 第 16 题
HMMT February 2016 — Guts Round — Problem 16
题目详情
- [ 9 ] Determine the number of integers 2 ≤ n ≤ 2016 such that n − 1 is divisible by 2, 3, 5, 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2016, February 20, 2016 — GUTS ROUND Organization Team Team ID#
解析
- [ 9 ] Determine the number of integers 2 ≤ n ≤ 2016 such that n − 1 is divisible by 2, 3, 5, 7. Proposed by: Evan Chen Answer: 9 Only n ≡ 1 (mod 210) work. Proof: we require gcd( n, 210) = 1. Note that ∀ p ≤ 7 the order of n n (mod p ) divides p − 1, hence is relatively prime to any p ≤ 7. So n ≡ 1 (mod p ) ⇐⇒ n ≡ 1 (mod p ) for each of these p .