1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ '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? $\endgroup$
    – TrostAft
    Mar 31, 2020 at 15:31
  • $\begingroup$ I don't see how you get $(p_1-1)(p_2-1)\geq\frac{p_1p_2}{2}$. $\endgroup$ Mar 31, 2020 at 15:32
  • $\begingroup$ @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. $\endgroup$ Mar 31, 2020 at 15:36
  • $\begingroup$ @TrostAft Hmm, I see the error. Can you offer a hint as to the correct proof? $\endgroup$ Mar 31, 2020 at 15:39
  • 1
    $\begingroup$ 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$. $\endgroup$
    – TrostAft
    Mar 31, 2020 at 15:48

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .