HMMT 二月 2002 · 冲刺赛 · 第 51 题

HMMT February 2002 — Guts Round — Problem 51

[10] Define ϕ ( n ) as the number of positive integers that are less than or equal to n/k 2001 2 and relatively prime to n . Find φ (2002 − 1). (Hint: φ (2003) = 2002.) 8

解析

Define ϕ ( n ) as the number of positive integers that are less than or equal to n/k 2001 2 and relatively prime to n . Find φ (2002 − 1). (Hint: φ (2003) = 2002.) 12 2001 2 2001 Solution: ϕ (2002 − 1) = ϕ (2001 · 2003) = the number of m that are relatively prime to both 2001 and 2003, where m ≤ 2003. Since φ ( n ) = n − 1 implies that n is prime, we must only check for those m relatively prime to 2001, except for 2002, which is 2 2001 2 relatively prime to 2002 − 1. So ϕ (2002 − 1) = ϕ (2001) + 1 = ϕ (3 · 23 · 29) + 1 = (3 − 1)(23 − 1)(29 − 1) + 1 = 1233 .