HMMT February

Number theory Difficulty 5.0 AIME Find the answer

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

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

$\varphi^{2001}\left(2002^{2}-1\right)=\varphi^{2001}(2001 \cdot 2003)=$ the number of $m$ that are relatively prime to both 2001 and 2003, where $m \leq 2003$ . Since $\phi(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 $2002^{2}-1$ . So $\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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.