# Prove that $n$ has at least four distinct prime factors

If $n$ is composite and $\phi{(n)} | (n - 1)$ then prove that $n$ has at least four distinct prime factors.

Attempt:

Since $n$ is not a prime, let's first take the case that $n$ is squarefree. Then $n = a_1 \cdot a_2 \cdots a_r$ where $a_i$ are the prime factors of $n$ listed in ascending order. Thus, $\dfrac{n-1}{\phi(n)} = \dfrac{a_1a_2\cdots a_r-1}{(a_1-1)(a_2-1)\cdots (a_n-1)}$. The denominator has a factor of $2^n$.

I am not sure how to continue from here.

• What about $n = 1$? – Michael Biro May 26 '16 at 0:53
• @MichaelBiro I think we suppose $n>1$? – Puzzled417 May 26 '16 at 1:01
• Note that $n$ would have to be squarefree, since if $p^2\mid n$ then $p\mid \phi(n)$ but not $n-1$. – rogerl May 26 '16 at 1:21
• This is related to Lehmer's totient problem. – rogerl May 26 '16 at 1:26
• @rogerl Why is it true that if $p^2 | n$ then $p | \phi(n)$? – Puzzled417 May 26 '16 at 1:38

To eliminate $3$ prime factors is pretty simple because since $\phi(n)<n-1$ it implies that $\phi(n)\le\frac n2$. If $3$ isn't one of the factors the smallest $\frac{\phi(n)}n$ could be is $\frac45\frac67\frac{10}{11}=0.6234$. If $5$ isn't a factor, the smallest is $\frac23\frac67\frac{10}{11}=0.5165$. If both $3$ and $5$ are factors, $\frac23\frac45\frac{16}{17}=0.5020$ is too big, so we only have to test $\phi(105)=48$, $\phi(165)=80$, and $\phi(195)=96$ to eliminate all remaining possibilities.

This solves the 2 prime factor case, which together with user5713492's answer, solves the problem:

Suppose we have primes $p$ and $q$ such that $\phi(pq)=(p-1)(q-1)|pq-1$. Then we have:

$$pq\equiv1\pmod{(p-1)(q-1)}$$

so

$$pq\equiv1\pmod{p-1}$$

and also

$$p\equiv1\pmod{p-1}$$

so

$$pq\equiv q\pmod{p-1}$$

hence

$$q\equiv1\pmod{p-1}$$

and so

$$q\geq p.$$

Similarly,

$$p\geq q,$$

so $p=q$, which contradicts that it must be squarefree, as noted in the comments.

• After reading user5713492's answer, I see that his answer actually solves the 2 prime case as well. I will leave this answer here for reference. – alphacapture May 26 '16 at 1:45
• I think there are typos here. For instance, it should be $pq−1 \equiv 0 \pmod{(p−1)(q-1)}$. – Puzzled417 May 26 '16 at 3:27
• @Puzzled417 Fixed – alphacapture May 26 '16 at 10:58