1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$ Jan 28, 2021 at 16:10

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – ASP
    Jan 27, 2021 at 21:18
  • 4
    $\begingroup$ 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 mathoverflow.net/questions/381456/… ). $\endgroup$ Jan 27, 2021 at 21:28
  • 1
    $\begingroup$ It appears the smallest counterexample is $3\cdot 5\cdot 7\cdot\dots\cdot 79=1608822383670336453949542277065$. WA confirms it's a counterexample $\endgroup$
    – Wojowu
    Jan 27, 2021 at 21:51
  • 1
    $\begingroup$ 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$ $\endgroup$
    – ASP
    Jan 27, 2021 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.