, 2008

Suppose $n$ has only one prime factor. Then $n = p^\alpha$ for some $\alpha > 1$ and prime $p$. Then $\varphi(n) = p^{\alpha-1}(p-1)$ divides $p^\alpha - 1$, which is impossible since $\alpha \ge 2$. Thus $n$ has at least two prime factors.

Suppose $n = p^\alpha q^\beta$, where $p \ne q$ are primes, $\alpha \ge 1$ and $\beta \ge 1$. Here $\varphi(n) = p^{\alpha-1}q^{\beta-1}(p-1)(q-1)$ and $n-1 = p^\alpha q^\beta - 1$. Thus $\varphi(n)|((n-1)(p-1))$ implies that $\alpha = 1 = \beta$ and $(p-1)(q-1)$ divides $pq-1$. This implies that $(p-1)|(q-1)$ and $(q-1)|(p-1)$, forcing $p=q$.

If $n$ has three distinct prime factors, say $p, q, r$, we see as in the earlier case $n = pqr$ and $(p-1)(q-1)(r-1)$ divides $pqr-1$. Taking $p-1=x, q-1=y$ and $r-1=z$, we see that
$$t = \frac{pqr - 1}{(p-1)(q-1)(r-1)} = 1 + \frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xy} + \frac{1}{yz} + \frac{1}{zx},$$
is an integer. We also observe that no prime can be even. (Otherwise $pqr-1$ is odd whereas one of $p-1, q-1, r-1$ is even.) Thus we may assume $3 \le p < q < r$, so that $x \ge 2, y \ge 4$ and $z \ge 6$. Thus
$$1 < t \le 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{12} + \frac{1}{24} = 1 + \frac{28}{24} < 3.$$
Thus $t=2$ and hence
$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xy} + \frac{1}{yz} + \frac{1}{zx} = 1.$$
If $p \ge 5$, we have $x \ge 4, y \ge 6$ and $z \ge 10$. In this case,
$$1 = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xy} + \frac{1}{yz} + \frac{1}{zx} \le \frac{1}{4} + \frac{1}{6} + \frac{1}{10} + \frac{1}{24} + \frac{1}{60} + \frac{1}{40} = \frac{72}{120} < 1.$$
Thus $p=3$ and $x=2$. We obtain
$$\frac{1}{y} + \frac{1}{z} + \frac{1}{2} \left( \frac{1}{y} + \frac{1}{z} \right) + \frac{1}{yz} = \frac{1}{2}.$$
This may be written in the form $(y-3)(z-3) = 11$. We thus get $y=4, z=14$. In turn, we have $q=5$ and $r=15$. But then $r$ is not a prime. Thus the number of distinct prime factors of $n$ is more than 3.