Phi-ratio

Let the distinct prime factors of $n$ be $p_1, \ldots, p_k.$ Then,

$\phi(n) = n\left(1-\dfrac{1}{p_1}\right)\ldots\left(1-\dfrac{1}{p_k}\right) = n\left(\dfrac{p_1-1}{p_1}\right)\ldots\left(\dfrac{p_k-1}{p_k}\right),$ so

$\dfrac{n}{\phi(n)} = \left(\dfrac{p_1}{p_1-1}\right)\ldots\left(\dfrac{p_k}{p_k-1}\right).$

Since this is an integer, it must be that $(p_1-1)\ldots(p_k-1)$ divides $p_1\ldots p_k.$ We investigate this very strong condition.

First, if all of the $p_i$ are odd, then $(p_1-1)\ldots(p_k-1)$ is even, while $p_1\ldots p_k$ is odd, so the condition cannot hold. Thus, one of the $p_i,$ say $p_1,$ must equal $2,$ and the other $p_i$ must be odd. Our condition becomes

$(2-1)(p_2-1)\ldots(p_k-1) \mid 2p_2\ldots p_k$ or

$(p_2-1)\ldots(p_k-1) \mid 2p_2\ldots p_k.$ Now, note that the right-hand side has exactly one factor of $2,$ since all of $p_2, \ldots, p_k$ are odd; since the left-hand side is composed of even factors, we can only have one factor on the left-hand side. That is, our condition reduces to just

$p_2-1 \mid 2p_2.$ Then there must be some positive integer $a$ such that $2p_2 = a(p_2-1),$ or $2p_2 = ap_2 - a.$ Taking mod $p_2,$ we get $a \equiv 0 \pmod p.$ So, we let $a = bp_2$ for some positive integer $b,$ and the equation becomes

$2p_2 = (bp_2)p_2 - bp_2$ which gives

$2 = b(p_2-1).$ This means that $p_2-1$ is either $1$ or $2$ ; in the first case, we get $p_2 = 2,$ which contradicts the assumption that the $p_i$ are distinct; therefore the second case must hold, so $p_2 = 3.$

Thus, $n = 2^c3^d$ for some positive integers $c, d.$ This implies that $\phi(n) = n \cdot \dfrac12 \cdot \dfrac23 = \dfrac n3,$ so $\dfrac{n}{\phi(n)} = 3.$ (This is an interesting discovery - if $\dfrac{n}{\phi(n)}$ is an integer, then it is an odd integer.) So, all $n$ in the form $2^c3^d$ work. Going through all cases, we get the possible values

$n = 6, 18, 54, 12, 36, 24, 72, 48, 96,$ the sum of which is $\boxed{366}.$

Let $\pi_2(n)$ denote the highest power of $2$ that divides $n$ . For example, $40= 2^3 \times 5$ , so $\pi_2(40)= 3$ . Observe that for $\dfrac{n}{\phi (n)}$ to be an odd integer, we must have $\pi_2(n)= \pi_2(\phi (n))$ .

*Lemma: * If $\gcd (a, 2)= 1$ and $b$ is any integer, $\pi_2(ab)= \pi_2(b)$ .

*Proof: * Trivial $$

*Lemma: * For all $a_1, a_2, \cdots , a_n$ , $\pi_2 (a_1 a_2 \cdots a_n)= \pi_2(a_1) + \pi_2(a_2) + \cdots + \pi_2(a_n)$ .

*Proof: * Also trivial; left to the reader

$$

*Claim: * If $\pi_2 (n)= \pi_2 (\phi (n))$ , then $n= 2^m p^j$ for some positive integers $m, j$ , where $p$ is a prime of the form $4k+3$ .

*Proof: * Let $n= 2^{a_0} \times p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n}$ , where $p_1, p_2, \cdots , p_n$ are odd primes and $a_0, a_1, \cdots , a_n$ are positive integers. We then have $\pi_2(n)= a_0$ . Since $\phi (n)$ is always even, $a_0$ cannot be zero. Again, since $\pi_2 \left ( \phi (2^m) \right ) = \pi_2 \left ( 2^m \left ( 1 - \dfrac{1}{2} \right ) \right ) = {m-1}$ , $n \neq 0$ . Now, note that $\begin{array}{lcl} \phi (n) &=& n \left ( 1 - \frac{1}{2} \right ) \left ( 1 - \frac{1}{p_1} \right ) \cdots \left ( 1 - \frac{1}{p_n} \right ) \\ & = & 2^{a_0-1} p_1^{a_1-1} p_2^{a_2-1} \cdots p_n^{a_n-1} p_1^{a_1-1} p_2^{a_2-1} \cdots p_n^{a_n-1} (p_1-1)(p_2-1)\cdots (p_n-1)\end{array}$ Since $\gcd (2, p_1^{a_1-1} p_2^{a_2-1} \cdots p_n^{a_n-1} )= 1$ , $\begin{array}{lcl} \pi_2(\phi (n))&= &a_0-1 + \pi_2((p_1-1)(p_2-1)\cdots (p_n-1)) \\ & = & a_0-1 + \pi_2 (p_1-1) + \pi_2 (p_2-1) + \cdots + \pi_2(p_n-1) \end{array}$ This has to be equal to $a_0$ , so $\pi_2 (p_1-1) + \pi_2 (p_2-1) + \cdots + \pi_2(p_n-1)= 1$ Observe that $p_1-1, p_2-1, \cdots , p_n - 1$ are all even, so $\pi_2(p_i-1) \geq 1$ for all $i$ . Then, $\sum \limits_{i=1}^{n} \pi_2 (p_i-1) \geq n$ Since this has to be equal to $1$ , we find out $n= 1$ . So, $n= 2^m p^n$ for some prime $p$ . Also, $\pi_2 (p-1)= 1$ . If $p$ is of the form $4k+1$ , $4 \mid p-1$ , and hence $\pi_2 (p-1) > 1$ . So, $p$ must be a prime of the form $4k+3$ . QED

Now, let $n= 2^m (4k+3)^n$ . We then find out $\phi (n)= 2^{m-1} (4k+3)^{n-1} (4k+2) = 2^m (4k+3)^{n-1}(k+1)$ . Then, $\begin{array}{lcl} \frac{n}{\phi (n)}&= & \frac{2^m (4k+3)^n}{2^m (4k+3)^{n-1}(k+1)} \\ & = & \frac{4k+3}{k+1} \\ & = & 4- \frac{1}{k+1} \end{array}$ The only possible solution is $k= 0$ , so $n= 2^m3^n$ for some positive integers $m$ and $n$ . Indeed, we can verify that in this case, $\dfrac{n}{\phi (n)}= 3$ . Quickly listing all possible such numbers from $2$ to $100$ , we find out that the set of valid $n$ is $\{6,12,18,24,36,48,54,72,96\}$ . The sum is $\boxed{366}$ .