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.)
A number or a short expression. Spacing and $ signs are ignored.
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: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.