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 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 nn
(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 .