Maths Olympiad Prep

Library / /10 of 860

Number theory Difficulty 4.5 AIME Find the answer

Give the set of all positive integers nn such that φ(n)=200221\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 nmn-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. 2002212002^{2}-1 is odd, and φ(2)=1200221\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,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.