Number theoryDifficulty 5.1AIME, harderProve itUnited States
Problem:
Define φk(n) as the number of positive integers that are less than or equal to n/k and relatively prime to n. Find φ2001(20022−1). (Hint: φ(2003)=2002.)
Solution
Solution:
φ2001(20022−1)=φ2001(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 relatively prime to 20022−1. So φ2001(20022−1)=φ(2001)+1=φ(3⋅23⋅29)+1=(3−1)(23−1)(29−1)+1=1233.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.