HMMT 二月 2001 · 代数 · 第 8 题
HMMT February 2001 — Algebra — Problem 8
题目详情
- How many integers between 1 and 2000 inclusive share no common factors with 2001? x y z z
解析
- How many integers between 1 and 2000 inclusive share no common factors with 2001? Solution: Two integers are said to be relatively prime if they share no common factors, that is if there is no integer greater than 1 that divides evenly into both of them. Note that 1 is relatively prime to all integers. Let ϕ ( n ) be the number of integers less than n that are relatively prime to n . Since ϕ ( mn ) = ϕ ( m ) ϕ ( n ) for m and n relatively prime , we have ϕ (2001) = ϕ (3 · 23 · 29) = (3 − 1)(23 − 1)(29 − 1) = 1232 . x y z z