Proof verification: $n$ has three discrete prime factors when $ϕ(n) \mid (n−1)$

Question

I found this problem in an Olympiad textbook:

Prove that if $n$ is not a prime and $ϕ(n)\mid(n−1)$ then $n$ has at least $3$ prime factors.

First I proved that $n$ has only discrete prime factors, which I have omitted here.

---

Proof:

Let us assume that that $n$ has, to the contrary, less than $3$ prime factors. Clearly $n$ is not prime so it cannot have $1$ prime factor. Hence $n$ must have $2$ prime factors. Let us call them $p_1$ and $p_2$.

Now, $\phi(n) = (p_1-1)(p_2-1) \Rightarrow (p_1-1)(p_2-1) \mid n-1$. Hence we can write $n-1 = k(p_1-1)(p_2-1)$ for some $k \in \mathbb{N}$.

Since $p_1 \neq p_2$ we can say that at least one of the primes $\neq 2$. Without loss of generality we can assume it as $p_1$. This means that $p_1 -1 \geq \frac{p_1}{2} \Rightarrow (p_1 -1)(p_2-1) \geq \frac{p_1p_2}{2} = \frac{n}{2}$.

Clearly then $k=1$, else $k(p_1-1)(p_2-1)$ would exceed $n-1$. This implies that $n-1 = (p_1-1)(p_2-1)$.

But that would mean

$$n-1 = p_1p_2 + 1 -(p_1+p_2)$$ $$\Rightarrow n-1 = n + 1 -(p_1+p_2)$$ $$\Rightarrow 2 = p_1+p_2$$

which is an absurdity. Hence we can say that $n-1$ must have more than $2$ prime factors.

---

I am not entirely convinced of the validity of this argument since the next question is that $n$ must have at least $4$ factors, which I thought would follow from a similar argument (it doesn't).

Answer 1

Indeed there is an error, quoting from my comment:

'Clearly then $k=1$, else $k(p_1−1)(p_2−1)>n−1$'. Is this true? We've assumed $p_1\neq 2$,but couldn't $p_2=2$? Then we would have $k(p_1−1)(p_2−1)=k(p_1−1)≥(kp_1p_2)/2$, which is acceptable for $k=2$ for strict equality?'

To fix this assume $p_2 = 2$ and $k = 2$. Then we know that: $$ n-1 = 2(p_1-1)(p_2-1) = 2(p_1 - 1) \implies n \text{ odd } $$ But this is a contradiction on the assumption that $n$ is factored by $p_2 = 2$. Thus $k = 1$ and your original argument holds.