PUMaC 2014 · 数论（B 组） · 第 4 题

PUMaC 2014 — Number Theory (Division B) — Problem 4

[ 4 ] Find the number of fractions in the following list that is in its lowest form. (ie. for , q gcd( p, q ) = 1. 1 2 1007 , , ..., 2014 2013 1008 x 2

解析

[ 4 ] Find the number of fractions in the following list that is in its lowest form. (ie. for , q gcd( p, q ) = 1. 1 2 1007 , , ..., 2014 2013 1008 Solution: The fractions that are not in lowest form have denominators divisible by at least one of 5, 1007 13 and 31 (since 2015 = 5 × 13 × 31). We calculate how many of those are there: b c + 5 1007 1007 1007 1007 1007 1007 b c + b c − b c − b c − b c + b c = 201 + 77 + 32 − 15 − 6 − 2 = 287. 13 31 65 403 155 2015 Hence there are 1007 − 287 = 720 fractions in the lowest form. 1 x 2