PUMaC 2013 · 团队赛 · 第 6 题

PUMaC 2013 — Team Round — Problem 6

How many positive integers n less than 1000 have the property that the number of positive n integers less than n which are coprime to n is exactly ? 3 1 1 1 1

解析

How many positive integers n less than 1000 have the property that the number of positive n integers less than n which are coprime to n is exactly ? 3 SOLUTION: From ∏ p − 1 1 = , p 3 p | n one of the p ’s must be 3. Similarly, from ∏ p − 1 1 = , p 2 p | n,p 6 =3 a b one of the remaining p ’s must be 2, and we must have n = 2 3 for some a, b ≥ 1 with n < 1000. The solutions are n = 6 , 12 , 24 , 48 , 96 , 192 , 384 , 768 , 18 , 36 , 72 , 144 , 288 , 576 , 54 , 108 , 216 , 432 , 864 , 162 , 324 , 648 , 486 , 972. There are 24 of them. ANSWER: 24 1 1 1