1

Lehmer's totient problem asks if there are any composite integers $n$ with $\phi(n) \ | \ n-1$.

It is known that any such $n$ must be odd. It must also be a charmichael number.

Assume $n=4m+3$ then $\phi(n) \ | \ n-1=2(2m+1)$ . Because $n$ is a carmichael number, we have $2^3 \ | \ \phi(n)$. It follows that $2^3 \ | \ 2(2m+1)$ which is not possible therefore we must have $n=4m+1$.

If the following conjecture is true, then Lehmer's totient problem is equivalent to asking whether there are any composite integers $n$ with $\phi(n)=(n-1)/2$.

Conjecture 1. Let $n=4m+1$ where $n$ and $m$ are positive integers. Then $\phi(n) >m$.

Theorem 1. Assume Conjecture 1 holds. If $n=4m+1$ is composite and $\phi(n) \ | \ n-1$, then $\phi(n)=2m$.

Proof. Because $\phi(n) >m$ and $\phi(n) \ | \ n-1=4m$, we must have $\phi(n)= 2m$ finishing the proof.

Remark. If Conjecture 1 can be proven then we have an almost complete proof to Lehmer's totient conjecture. The possibility of $\phi(n)= 2m$ can be disproven thus providing a complete proof to Lehmer's totient problem.

There are no counterexamples to Conjecture 1 for all $m < 10^{7}$ . I need assistance in proving this conjecture or in finding at least one counterexample. For the interested readers, Conjecture 1 may be generalized to:

Conjecture 2. Let $n=am+r$ where $a$, $m$ and $r$ are positive integers with $m>a \ge 4$ and $a \ \nmid \ r$. Then $\phi(n) >m$.

ASP
  • 319
  • 1
    Conjecture 1 is false: The quotient $\phi(n)/n$ can go to $0$ for $n$ large: If $n$ is divisible by the first $k$ odd primes $p_1,\ldots,p_k$, the quotient is bounded by $\prod_{i=1}^k (1-p_i^{-1})$, and this product converges to $0$ (just quite slowly). – Peter Scholze Jan 28 '21 at 16:10

1 Answers1

9

This is false. Take $n$ equal to the product of first $k$ odd primes, or 3 times larger (so that $n-1$ is divisible by 4). For large $k$, $\varphi(n)/n=(1-1/3)(1-1/5) \ldots (1-1/p_{k+1})$ tends to 0. The same with conjecture 2.

Fedor Petrov
  • 102,548
  • your proof disproving Conjecture 1 is not rigorous. I don't follow. Could you provide a rigorous proof. It would also be nice if you provided at least one counterexample. Nonetheless a rigorous proof will suffice. – ASP Jan 27 '21 at 21:18
  • 4
    Fedor's proof seems rigorous to me. It would be helpful to know what part you did not follow. The least elementary part of his argument is the fact that $(1-1/3)(1-1/5)\ldots(1-1/p_{k+1})$ tends to $0$; this is equivalent to the divergence of the sum of reciprocals of primes, a result essentially due to Euler (which was recently discussed here https://mathoverflow.net/questions/381456/what-is-the-simplest-proof-that-the-density-of-primes-goes-to-zero/ ). – Ofir Gorodetsky Jan 27 '21 at 21:28
  • 1
    It appears the smallest counterexample is $3\cdot 5\cdot 7\cdot\dots\cdot 79=1608822383670336453949542277065$. WA confirms it's a counterexample – Wojowu Jan 27 '21 at 21:51
  • 1
    I have now understood the proof. There are infinitely many counterexamples!. The next counterexample after $3 \cdot 5 \cdot 7 \cdots 79 $ is $3 \cdot 5 \cdots 103$ – ASP Jan 27 '21 at 22:15