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

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).

• '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) \geq (kp_1p_2)/2$, which is acceptable for $k = 2$ for strict equality? Mar 31, 2020 at 15:31
• I don't see how you get $(p_1-1)(p_2-1)\geq\frac{p_1p_2}{2}$. Mar 31, 2020 at 15:32
• @GregoryGrant Ah, I see the mistake. I knew that something was incorrect. $(p_1-1)(p_2-1)\geq\frac{p_1p_2}{4}$, not $\frac{p_1p_2}{2}$ by multiplication. Mar 31, 2020 at 15:36
• @TrostAft Hmm, I see the error. Can you offer a hint as to the correct proof? Mar 31, 2020 at 15:39
• I have a bad idea; If you proceed assuming $k = 2$, I believe you can show $n$ must be odd; which is a contradiction under the assumption that $p_2 = 2$, which is the only way $k = 2$. Mar 31, 2020 at 15:48

'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.