HMMT 十一月 2016 · 冲刺赛 · 第 8 题

HMMT November 2016 — Guts Round — Problem 8

[ 7 ] Danielle picks a positive integer 1 ≤ n ≤ 2016 uniformly at random. What is the probability that gcd( n, 2015) = 1?

解析

[ 7 ] Danielle picks a positive integer 1 ≤ n ≤ 2016 uniformly at random. What is the probability that gcd( n, 2015) = 1? Proposed by: Evan Chen 1441 Answer: 2016 We split the interval [1 , 2016] into [1 , 2015] and 2016. The number of integers in [1 , 2015] that are 4 12 30 relatively prime to 2015 is φ (2015) = · · · 2015 = 1440. Also, 2016 is relatively prime to 2015, so 5 13 31 there are a total of 1441 numbers in [1 , 2016] that are relatively prime to 2015. Then the probability 1441 of picking a number relatively prime to 2015 is . 2016