Indija TS 2008

Suppose $n$ has only one prime factor. Then $n=p^{\alpha }$ for some $\alpha >1$ and prime $p$. Then $\phi (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 $\phi (n)=p^{\alpha -1}{q}^{\beta -1}(p-1)(q-1)$ and $n-1=p^{\alpha }{q}^{\beta }-1$. Thus $\phi (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.