Maths Olympiad Prep

Library / /222 of 860

Number theory Difficulty 5.0 AIME Find the answer

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)\phi^{2001}\left(2002^{2}-1\right). (Hint: ϕ(2003)=2002\phi(2003)=2002.)

A number or a short expression. Spacing and $ signs are ignored.

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