Maths Olympiad Prep

Library / /72 of 94

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:

Define φk(n)\varphi^{k}(n) as the number of positive integers that are less than or equal to n/kn / k and relatively prime to nn. Find φ2001(200221)\varphi^{2001}\left(2002^{2}-1\right). (Hint: φ(2003)=2002\varphi(2003)=2002.)

Solution

Solution:

φ2001(200221)=φ2001(20012003)=\varphi^{2001}\left(2002^{2}-1\right)=\varphi^{2001}(2001 \cdot 2003)= the number of mm that are relatively prime to both 20012001 and 20032003, where m2003m \leq 2003. Since φ(n)=n1\varphi(n)=n-1 implies that nn is prime, we must only check for those mm relatively prime to 20012001, except for 20022002, which is relatively prime to 2002212002^{2}-1. So φ2001(200221)=φ(2001)+1=φ(32329)+1=(31)(231)(291)+1=1233\varphi^{2001}\left(2002^{2}-1\right)=\varphi(2001)+1=\varphi(3 \cdot 23 \cdot 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.