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)}$ for $n$ in the set $\{2, \ldots, 1000\}$ and all values of $n$ for which this maximum is attained.
Problem
Source: Canada RepĂȘchage 2017/2
Tags: number theory
13.04.2017 15:49
13.04.2017 23:58
It is well known that $\varphi(n) = n\cdot\prod_{i=1}^k \left(1-\tfrac{1}{p_i}\right)$ where $n$ has prime factors $p_1, p_2, \cdots , p_k$. Thus, we have that $$\frac{n}{\varphi(n)}=\frac{1}{\prod \left(1-\tfrac{1}{p_i}\right)}=\frac{\prod p_i}{\prod (p_i-1)}$$When $p$ is small, $\frac{p}{p-1}=1+\frac{1}{p-1}$ is bigger so we pick the smallest four primes since picking $11$ will make $n>1000$. Thus the maximum value for $\frac{n}{\varphi(n)}$ is $\frac{2\cdot 3\cdot 5\cdot 7}{1\cdot 2\cdot 4\cdot 6}=\frac{35}{8}$. This maximal value is achieved at any multiple of $2\cdot 3\cdot 5\cdot 7=210$ less than $1000$ since multiplying by $2,3,4$ does not introduce any new primes, thereby not changing the value of $\frac{\prod p_i}{\prod (p_i-1)}$.
29.10.2017 22:40
Quote: This maximal value is achieved at any multiple of $2\cdot 3\cdot 5\cdot 7=210$ less than $1000$ since multiplying by $2,3,4$ does not introduce any new primes, thereby not changing the value of $\frac{\prod p_i}{\prod (p_i-1)}$. But if we make $n$ greater, doesn't that make the value of $\frac{n}{\varphi(n)}$ greater? If $n = 840$, doesn't $\frac{n}{\varphi(n)}=\frac{35}{2}?$
30.10.2017 02:02
No, the value remains the same (see post above). For the particular example you gave, $\phi(840) = 840 \cdot (1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{7}) = 192$, so $\frac{840}{192} = 35/8$, the same as for $210$.