Competition problem — Number theory

Library / /320 of 860

Number theory Difficulty 5.1 AIME, harder Find the answer

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}$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.