HMMT 二月 1998 · ADV 赛 · 第 5 题
HMMT February 1998 — ADV Round — Problem 5
题目详情
- How many positive integers less than 1998 are relatively prime to 1547? (Two integers 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 relatively prime 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 positive integers less than 1998 that are not divisible by 7, 13, or 17. By the Principle of Inclusion-Exclusion, we first subtract the numbers that are divisible by one of 7, 13, and 17, add back those that are divisible by 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