2

Part of 2017 Canadian Mathematical Olympiad Qualification

Problems(1)

Maximize n over phi n

Source: Canada Repêchage 2017/2

For any positive integer n, let

\varphi(n)

be the number of integers in the set

\{1, 2, \ldots , n\}

whose greatest common divisor with

n

is 1. Determine the maximum value of

\frac{n}{\varphi(n)}

n

\{2, \ldots, 1000\}

and all values of

n

for which this maximum is attained.