Library / /830 of 1394

, 2020

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Let $\varphi(n)$ denote the number of positive integers less than or equal to $n$ which are relatively prime to $n$ . Let $S$ be the set of positive integers $n$ such that $\frac{2 n}{\varphi(n)}$ is an integer. Compute the sum
$\sum_{n \in S} \frac{1}{n}$

Solution

Solution:
Let $T_{n}$ be the set of prime factors of $n$ . Then
$\frac{2 n}{\phi(n)}=2 \prod_{p \in T} \frac{p}{p-1}$
We can check that this is an integer for the following possible sets:
$\varnothing,\{2\},\{3\},\{2,3\},\{2,5\},\{2,3,7\} .$
For each set $T$ , the sum of the reciprocals of the positive integers having that set of prime factors is
$\prod_{p \in T}\left(\sum_{m=1}^{\infty} \frac{1}{p^{m}}\right)=\prod_{p \in T} \frac{1}{p-1}$
Therefore the desired sum is
$1+1+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{12}=\frac{10}{3}$

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.