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

HMMT February 2002 — Guts Round — Problem 49

个人笔记

[7] Two integers are relatively prime if they don’t share any common factors, i.e. iftheir greatest common divisor is 1. Define ϕ ( n ) as the number of positive integers that areless than n and relatively prime to n . Define ϕ ( n ) as the number of positive integers thatdare less than dn and relatively prime to n .
What is the least n such that ϕ ( n ) = 64000, where x = ϕ ( n ), where y = ϕ ( n )?
x y 2

解析

Two integers are relatively prime if they don’t share any common factors, i.e. if theirgreatest common divisor is 1. Define ϕ ( n ) as the number of positive integers that are lessthan n and relatively prime to n . Define ϕ ( n ) as the number of positive integers that aredless than dn and relatively prime to n .
What is the least n such that ϕ ( n ) = 64000, where x = ϕ ( n ), where y = ϕ ( n )?
x y
Solution: For fixed n , the pattern of integers relatively prime to n repeats every nintegers, so ϕ ( n ) = dϕ ( n ). Therefore the expression in the problem equals ϕ ( n ) . The cube 3
root of 64000 is 40. ϕ ( p ) = p − 1 for any prime p . Since 40 is one less than a prime, the leastdn such that ϕ ( n ) = 40 is 41 . 2