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



A new perspective on Lehmer's totient problem
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.


