Maths Olympiad Prep

Library / HMMT February /16 of 1302

HMMT February

Number theory Difficulty 4.5 AIME Find the answer

Give the set of all positive integers nn such that φ(n)=20022−1\varphi(n)=2002^{2}-1.

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

Solution

The empty set, ∅\varnothing. If mm is relatively prime to nn and m<nm<n, then n−mn-m must likewise be relatively prime to nn, and these are distinct for n>2n>2 since n/2,nn / 2, n are not relatively prime. Therefore, for all n>2,φ(n)n>2, \varphi(n) must be even. 20022−12002^{2}-1 is odd, and φ(2)=1≠20022−1\varphi(2)=1 \neq 2002^{2}-1, so no numbers nn fulfill the equation.

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.