Some questions on Euler's phi function

587 Views Asked by At

I was reading Number Theory by George E. Andrews (Dover 1994,) problem set 6-1, p. 81. (I'm not a student; I just find problems like these entertaining like some people enjoy crosswords or Sudoku.) Question No. 1 is to prove that if $\phi(m)|m-1$ then there is no prime $p$ such that $p^2|m$. I omit the proof here; it is not that difficult but I mention it because the result is useful for proving question No. 2:

Prove that if $m$ is not prime and $\phi(m)|m-1$, then $m$ has at least three distinct prime factors.

Suppose $m$ has exactly two distinct prime factors; $m=pq$, and $p<q$. If $p=2$ and $q$ is an odd prime, then $\phi(m)=q-1$ and $m-1=2q-1$ but clearly $q-1\nmid 2q-1$. If $p$ and $q$ are both odd primes, then $p\ge 3$, $q\ge 5$ and $$1 < \frac{m-1}{\phi(m)}=\frac{pq-1}{(p-1)(q-1)}\le \frac{3\cdot 5 - 1}{(3-1)(5-1)}=\frac{14}{8}<2.$$ In this case, $\phi(m)\nmid m-1$ because the quotient is strictly bounded between $1$ and $2$. The proof is completed by contradiction.

Question No. 3 is on the same premises to prove that $m$ has at least four distinct prime factors.

Please leave questions No. 1 and 3 as "homework" or use a spoiler warning if you must answer them. What I am really asking is first to comment on and correct my proof above, and second, a soft question, "Where does this line of hypotheses and proofs lead beyond question No. 3?"

1

There are 1 best solutions below

0
On

I will not answer your questions $1$ and $3$, as you have requested (they are answered at MSE here, in case you want to see it later). The soft question may be answered by a survey article on Lehmer's totient problem, which says that $$ \phi(m)\mid m-1 $$ if and only if $m$ is prime. There are numerous results on how many prime divisors such $m$ would have, if $m$ were composite.