HMMT 二月 1998 · ADV 赛 · 第 5 题
HMMT February 1998 — ADV Round — Problem 5
题目详情
英文原题
- How many positive integers less than 1998 are relatively prime to 1547? (Twointegers are relatively prime if they have no common factors besides 1.)
解析
英文解析
- How many positive integers less than 1998 are relatively prime to 1547? (Two integers are relativelyprime if they have no common factors besides 1.)
Answer: 1487 . The factorization of 1547 is 7 · 13 · 17, so we wish to find the number of positiveintegers less than 1998 that are not divisible by 7, 13, or 17. By the Principle of Inclusion-Exclusion, wefirst subtract the numbers that are divisible by one of 7, 13, and 17, add back those that are divisibleby two of 7, 13, and 17, then subtract those divisible by three of them. That is,
⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋
1997 1997 1997 1997 1997 1997 1997
1997 − − − + + + − ,
7 13 17 7 · 13 7 · 17 13 · 17 7 · 13 · 17
or 1487. 1