2
$\begingroup$

Lehmer's totient problem asks if there exists a composite number $m$ such that $\phi(m)$ divides $m-1$. Lower bounds on $m$ has been established but we do not know if a solution exists. Clearly, if we find a divisor of $\phi(m)$ which does not divide $m-1$ then $m$ cannot be a solution of the problem. I started counting the number of divisors of $\phi(m)$ which do not divide. Soon I noticed pattern - Composites of the form :

  • $m = 8k+3$ has at least $4$ divisors of $\phi(m)$ which do not divide $m-1$
  • $m = 6k+5$ has at least $5$ divisors of $\phi(m)$ which do not divide $m-1$
  • $m = 12k+7$ has at least $6$ divisors of $\phi(m)$ which do not divide $m-1$
  • $m = 20k+3$ has at least $7$ divisors of $\phi(m)$ which do not divide $m-1$
  • $m = 24k+23$ has at least $8$ divisors of $\phi(m)$ which do not divide $m-1$

$$ \cdots $$

  • $m = 48k+11$ has at least $14$ divisors of $\phi(m)$ which do not divide $m-1$

In fact each of the above arithmetic progressions is the smallest (lowest coefficient of $k$) for a given $n$ and there could be more than one arithmetic progression with the above property.

Claim: For $n \ge 1$ there is an arithmetic progression of odd numbers $m_k = ak + b $ such that if $m_k$ composite then there are at least $n$ divisors of $\phi(m_k)$ which do not divide $m_k-1$.

Question: Can we find a counter example i.e. is there an integer $n$ for which at we cannot find such an arithmetic progression?

Note: Question was posted in MSE 3 weeks ago but did not get an answer. Hence posting in MO

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Sure. If $m_k=2^{n+1}k$, then $2,2^2,\dots,2^n$ are $n$ divisors of $\phi(m_k)$ which do not divide $m_k-1$. $\endgroup$
    – GH from MO
    Commented Sep 1, 2019 at 8:34
  • $\begingroup$ @GHfromMO Thanks but, if you see all the examples of $m_k$ in the post, these are all progressions of odd numbers which is what I am looking for. Now I have mentioned this explicitly $\endgroup$
    – Nilotpal Kanti Sinha
    Commented Sep 2, 2019 at 6:18
  • $\begingroup$ OK. If $m_k=3^{n+1}(2k+1)$, then $3,3^2,\dots,3^n$ are $n$ divisors of $\phi(m_k)$ which do not divide $m_k-1$. $\endgroup$
    – GH from MO
    Commented Sep 2, 2019 at 6:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .