On Almost Lehmer Numbers

Tomohiro Yamada Center for Japanese Language and Culture Osaka University 562-8558, 8-1-1, Aomatanihigashi Minoo, Osaka Japan

                     tyamada1093@gmail.com

Abstract

We consider composite numbers n such that φ(n) divides ℓ(n−1) for some squarefree divisor ℓ of n − 1. We discuss two cases, according to whether the number of prime factors of ℓ is bounded or not. We give a few instances and upper bounds for the number of such integers below a given number.

1 Introduction

Let φ(n) denote the Euler totient function of n. Clearly, φ(p) = p − 1 for any prime p. Lehmer [8] conjectured that there exists no composite number n such that φ(n) divides n − 1 and showed that such an integer must be an odd squarefree integer with at least seven prime factors. In other words, if φ(n) | (n − 1) and n is composite, then n is odd and ω(n) = Ω(n) ≥ 7, where ω(n) and Ω(n) respectively denote the number of distinct and not necessarily distinct prime factors of n.

For such an integer n, Cohen and Hagis [4] showed that ω(n) ≥ 14 and n > 10^{20}, Renze’s notebook [15] shows that ω(n) ≥ 15 and n > 10^{26}, and Pinch claims that n > 10^{30} at his research page [13]. Pomerance [14] showed that the number of such an integer n ≤ x is O(x^{1/2} log^{3/4} x) and n ≤ r^{2^{r}} if 2 ≤ ω(n) ≤ r additionally. Luca and Pomerance [9] showed that the number of such an integer n ≤ x is at most

\frac{x^{1/2}}{log^{1/2+o(1)} x}.

Furthermore, Burek and Żmija [2] showed that n ≤ 2^{2^{r}} − 2^{2^{r−1}} if φ(n) divides n − 1 and 2 ≤ ω(n) ≤ r.

Weakening the condition φ(n) | (n − 1), Grau and Oller-Marcén [6] introduced the k-Lehmer property that φ(n) | (n − 1)^{k} and called a composite number with this property to be a k-Lehmer number. The first few 2-Lehmer numbers are 561, 1105, 1729, 2465, … (sequence \underline{A173703}). McNew [10] showed that for each k, the number of k-Lehmer numbers is O(x^{1−1/(4k−1)}) and the number of integers which are k-Lehmer numbers for some k is at most x exp(−(1 + o(1)) log x log log log x/ log log x). McNew and Wright [11] showed that for each k ≥ 3, there exist at least x^{1/(k−1)+o(1)} integers n ≤ x which are k-Lehmer but not (k − 1)-Lehmer numbers.

In this paper, we would like to discuss intermediate properties between the 1-Lehmer (that is, ordinary Lehmer) property and 2-Lehmer property.

We call a composite number n to be an almost Lehmer number if φ(n) divides ℓ(n−1) for some squarefree divisor ℓ of n−1 and an r-nearly Lehmer number if φ(n) divides ℓ(n−1) for some squarefree divisor ℓ of n−1 with ω(ℓ) ≤ r. The ordinary Lehmer property is equivalent to the 0-nearly Lehmer property and an almost Lehmer number can be called an ∞-nearly Lehmer number.

The first few almost Lehmer numbers are

1729, 12801, 247105, 1224721, 2704801, 5079361, 8355841, …,

given in \underline{A337316}. There exist exactly 38 almost Lehmer numbers below 2^{32}. There exist only five 1-nearly Lehmer numbers 1729, 12801, 5079361, 34479361, and 3069196417 below 2^{32} as given in \underline{A338998}.

For r = 1, 2, …, ∞, let U_{r} be the set of composite numbers n for which φ(n) divides ℓ(n − 1) for some squarefree divisor ℓ of n − 1 with ω(ℓ) ≤ r. Thus, U_{∞} denotes the set of almost Lehmer numbers. We also use the general notion that S(x) = {n ≤ x, n ∈ S} denote the set of integers S up to x for a set S of positive integers. Then McNew’s upper bound for 2-Lehmer numbers immediately yields that #U_{r}(x) ≤ #U_{∞}(x) = O(x^{6/7}). The purpose of this paper is to give stronger upper bounds for #U_{r}(x) and #U_{∞}(x).

Theorem 1. Let a_{r} be the number of partitions of the multiset {1, 1, 2, 2, …, r, r} of r integers repeated twice. Then, there exist two absolute constants c and c_{1} such that for each integer r ≥ 1,

#U_{r}(x) < ca_{r}(x log x)^{2/3}(c_{1} log log x)^{2r+2/3}.  (1)

Moreover, we have

#U_{∞}(x) < x^{4/5} exp ((\frac{4}{5} + o(1)) \frac{log x log log log x}{log log x}) ,  (2)

where o(1) → 0 ad x → ∞.

The first few terms of the sequence (a_{r}) are 2, 9, 66, 712, 10457, … given in \underline{A020555}. Bender’s asymptotic formula [1, Theorem 1] yields that

log a_{r} < 2r (log(2r) − log log(2r) − 1 − \frac{log 2}{2} + o(1))  (3)

as r grows. Hence, we obtain the following estimates.

Corollary 2. Setting c and c_{1} as in Theorem 1, we have

#U_{1}(x) < 2c(x log x)^{2/3}(c_{1} log log x)^{2r+2/3}  (4)

and

#U_{r}(x) < (\frac{(e\sqrt{2} + o_{r}(1))r}{log r})^{2r} (x log x)^{2/3}(c_{1} log log x)^{2r+2/3},  (5)

where o_{r}(1) tends to zero as r tends to infinity.

Our estimates depend on numbers of multiplicative partitions of integers, which will be discussed in the next section. Thus, fast growth of a_{r} prevents us from showing that #U_{∞}(x) < x^{2/3+o(1)}.

On the other hand, the above instances lead us to conjecture that there exist infinitely many almost Lehmer numbers. Moreover, there may be infinitely many 1-nearly Lehmer numbers, although such integers are distributed very rarely below our search limit. However, these also seem to be difficult to prove or disprove; it is even not known whether there exist infinitely many 2-Lehmer numbers or not!

2 Preliminary estimates

Let τ(s) be the number of multiplicative partitions of s = s_{1}s_{2} ⋯ s_{r} with s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{r}. The values of τ(s) for positive integers s are given in \underline{A001055}.

Lemma 3. For each integer s ≥ 1, let S(s; x) denote the set of positive integers n ≤ x such that s divides φ(n). Then

#S(s; x) ≤ \frac{τ(s)x(c_{1} log log x)^{Ω(s)}}{s} ,  (6)

where c_{1} is an absolute constant.

Proof. We observe that if s | φ(n), then q_{1}^{f_{1}}q_{2}^{f_{2}} ⋯ q_{t}^{f_{t}}q_{t+1} ⋯ q_{r} | n for some integers f_{1}, f_{2}, …, f_{t} ≥ 2 and distinct primes q_{1}, q_{2}, …, q_{r} such that

s | q_{1}^{f_{1}−1}q_{2}^{f_{2}−1} ⋯ q_{t}^{f_{t}−1}(q_{1} − 1)(q_{2} − 1) ⋯ (q_{r} − 1).

Moreover, we can take such q_{i}’s in the way that there exists a factorization of s = s_{1}s_{2} ⋯ s_{r+1} with 1 < s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{r} such that q_{i} ≡ 1 (mod s_{i}) for i = 1, 2, …, r and s_{r+1} divides q_{1}^{f_{1}−1}q_{2}^{f_{2}−1} ⋯ q_{t}^{f_{t}−1}.

For each factorization s = s_{1}s_{2} ⋯ s_{r+1}, the number of such integers n ≤ x does not exceed

∑_{\begin{matrix}q_{i}≤x, \\ q_{i}≡1 (mod s_{i})(i=1,2,...,r) \end{matrix}} \frac{x}{q_{1}q_{2} ⋯ q_{r}s_{r+1}} = \frac{x}{s_{r+1}} ∏_{i=1}^{r} ( ∑_{\begin{matrix}q_{i}≤x, \\ q_{i}≡1 (mod s_{i}) \end{matrix}} \frac{1}{q_{i}} ) .

We obtain from Erdős, Granville, Pomerance, and Spiro [5, (3.1)] that for i = 1, 2, …, r,

∑_{\begin{matrix}q_{i}≤x, \\ q_{i}≡1 (mod s_{i}) \end{matrix}} \frac{1}{q_{i}} < \frac{c_{1} log log x}{s_{i}}  (7)

with some absolute constant c_{1}. Thus, we conclude that the number of integers n ≤ x such that s divides φ(n) corresponding to each factorization s = s_{1}s_{2} ⋯ s_{r+1} can be bounded from above by

\frac{x(c_{1} log log x)^{r}}{s_{1}s_{2} ⋯ s_{r}s_{r+1}} = \frac{x(c_{1} log log x)^{r}}{s} .

Now the lemma immediately follows noting that r ≤ Ω(s).

We must note that although τ(s) is relatively small when Ω(s) is small but not when Ω(s) is large. Indeed, Canfield, Erdős, and Pomerance [3] showed that τ(s) = s exp(−(1 + o(1)) log s log log log s/ log log s) for highly factorable integers s, which are given in \underline{A033833}. So that, the above lemma cannot be used in order to bound the number of integers n such that φ(n) are multiples of s for an arbitrary integer s. Nevertheless, we can show the following upper bound for a certain sum involving τ(s).

Lemma 4. As x tends to infinity, we have

∑_{s≤x} \frac{τ(s)}{s} < \frac{(1 + o(1))e^{2\sqrt{log x}} log^{1/4} x}{2\sqrt{π}}.  (8)

Proof. Oppenheim [12] proved that

∑_{s≤x} τ(s) = \frac{(1 + o(1))xe^{2\sqrt{log x}}}{2\sqrt{π} log^{3/4} x} .  (9)

By partial summation, we immediately obtain (8).

3 Proof of the theorem

Let r be a positive integer or ∞, x denotes a sufficiently large real number, and n ≤ x be an r-nearly Lehmer number. In this section, the implied constants in ≪ and the O-symbols are absolute and each o(1) tends to zero as x goes to infinity.

We begin by writing (n − 1)/φ(n) = k/ℓ, where k and ℓ are coprime integers and ℓ is a squarefree integer with at most r distinct prime factors dividing n − 1. We note that n must be odd and squarefree since φ(n) and n are coprime and n is composite.

Take an arbitrary divisor d of n and write n = md. Since n is squarefree, we have ℓ(md − 1) = kφ(n) = kφ(m)φ(d) and

md ≡ 1 (mod \frac{φ(d)}{ℓ_{0}}) ,  (10)

where ℓ_{0} = gcd(ℓ, φ(d)).

It is clear that ℓ_{0} | ℓ | (n − 1) and therefore both φ(d)/ℓ_{0} and ℓ_{0} divide md − 1. Let a || b denote that a | b and gcd(a, b/a) = 1. We observe that if p^{e} || φ(d), then p^{e−1} | φ(d)/ℓ_{0} | (md − 1) and if p || φ(d), then p | φ(d) | ℓ(n − 1) | (n − 1)^{2} = (md − 1)^{2} and therefore p | (md − 1). Hence, decomposing ℓ_{0} = ℓ_{1}ℓ_{2}, where each prime factor p of ℓ_{0} divides ℓ_{1} if and only if p || φ(d), we obtain

md ≡ 1 (mod \frac{φ(d)}{ℓ_{2}}) .  (11)

Now let L_{1} > x^{1/3} and L_{2} = L_{1}^{2} be real numbers which will be chosen later in different manners according to whether r is an integer or r = ∞. We can easily see that n cannot have a prime factor p > L_{2}. If n = mp with p > L_{2}, then the above observation yields that mp ≡ 1 (mod (p − 1)/ℓ_{2}). Since p ≡ 1 (mod (p − 1)/ℓ_{2}) clearly, we have m ≡ 1 (mod (p − 1)/ℓ_{2}) and therefore m ≥ (p − 1)/ℓ_{2}. However, we see that p ≡ 1 (mod ℓ_{2}^{2}) since ℓ_{2}^{2} | φ(p) = p − 1. Thus, we must have p < m^{2} = (n/p)^{2} < (x/p)^{2} and p < x^{2/3} ≤ L_{2}, which is a contradiction.

Hence, n must have a prime factor p ≤ L_{2}. If n ≥ L_{1} and n has no prime divisor p ≥ L_{1}, then the smallest divisor d ≥ L_{1} of n must satisfy L_{1} ≤ d ≤ L_{1}^{2} = L_{2}. Clearly, if n has a prime factor p in the range L_{1} ≤ d ≤ L_{2}, then n has a divisor d = p with L_{1} ≤ d ≤ L_{2}. Thus, we observe that n has a divisor d in the range L_{1} ≤ d ≤ L_{2} if n ≥ L_{1}.

For each d, the number of integers n = md ≤ x satisfying (11) is at most 1+⌊ℓ_{2}x/(dφ(d))⌋. We note that ℓ_{2} ≤ \sqrt{φ(d)} ≤ L_{1}. Hence, using the inequality d/φ(d) ≪ log log d ≤ log log x, which follows from Theorem 328 of Hardy and Wright [7], we have

\begin{aligned}#U_{r}(x) & ≤ L_{1} + ∑_{ℓ_{2}≤L_{1}} ∑_{\begin{matrix}L_{1}≤d≤L_{2}, \\ ℓ_{2}^{2}|φ(d) \end{matrix}} (1 + \frac{ℓ_{2}x}{dφ(d)}) \\ & ≪ ∑_{ℓ_{2}≤L_{1}} (#S(ℓ_{2}^{2}; L_{2}) + ∑_{\begin{matrix}L_{1}≤d≤L_{2}, \\ ℓ_{2}^{2}|φ(d) \end{matrix}} \frac{ℓ_{2}x log log x}{d^{2}} ) . \end{aligned}  (12)

Let us estimate #U_{r}(x) for r < ∞. Recalling the definition of a_{r}, it is clear that τ(s^{2}) = a_{ω(s)} for any squarefree integer s. Thus, we have τ(ℓ_{2}^{2}) ≤ τ(ℓ^{2}) ≤ a_{r}. Using Lemma 3 and partial summation, we obtain

#U_{r}(x) ≪ a_{r} ∑_{ℓ_{2}≤L_{1}} (\frac{L_{2}(c_{1} log log x)^{Ω(ℓ_{2}^{2})}}{ℓ_{2}^{2}} + \frac{x(c_{1} log log x)^{Ω(ℓ_{2}^{2})+1}}{L_{1}ℓ_{2}} )

≪ a_{r} (L_{2}(c_{1} log log x)^{2r} + \frac{x(log x)(c_{1} log log x)^{2r+1}}{L_{1}} ) .

(13)

Taking L_{1} = (c_{1}x log x log log x)^{1/3}, we obtain the theorem.

Finally, we shall estimate #U_{∞}(x). Since ℓ_{2}^{2} | φ(d), we have φ(d)/ℓ_{2} ≥ \sqrt{φ(d)} ≫ (d/ log log d)^{1/2} using Theorem 328 of Hardy and Wright [7] again. Now, instead of the bottom line of (12), we obtain

#U_{∞}(x) ≪ ∑_{ℓ_{2}<L_{1}} (#S(ℓ_{2}^{2}; L_{2}) + ∑_{\begin{matrix}L_{1}≤d≤L_{2}, \\ ℓ_{2}^{2}|φ(d) \end{matrix}} \frac{x(log log x)^{1/2}}{d^{3/2}} )

≪ ∑_{ℓ_{2}≤L_{1}} \frac{τ(ℓ_{2}^{2})}{ℓ_{2}^{2}} (L_{2}(c_{1} log log x)^{Ω(ℓ_{2})} + \frac{x(c_{1} log log x)^{Ω(ℓ_{2})+1/2}}{L_{1}^{1/2}} ) .

(14)

Since ℓ_{2} is squarefree, we have Ω(ℓ_{2}^{2}) = 2ω(ℓ_{2}). Hence, from Hardy and Wright [7, Chapter 22.10], we see that

Ω(ℓ_{2}^{2}) < \frac{2(1 + o_{ℓ_{2}}(1)) log ℓ_{2}}{log log ℓ_{2}} < \frac{(1 + o(1)) log L_{2}}{log log x} ,  (15)

where the former o_{ℓ_{2}}(1) tends to zero as ℓ_{2} goes to infinity but the latter o(1) tends to zero as L_{2} (and therefore x) goes to infinity. By Lemma 4, we have

∑_{ℓ_{2}<L_{1}} \frac{τ(ℓ_{2}^{2})}{ℓ_{2}^{2}} ≤ ∑_{s<L_{2}} \frac{τ(s)}{s} ≪ e^{2\sqrt{log x}} log^{1/4} x.  (16)

Inserting (15) and (16) into (14), we obtain

#U_{∞}(x) ≪ e^{(1+o(1)) log L_{2} log log log x/ log log x} (L_{2} + \frac{x}{L_{1}^{1/2}} ) .  (17)

Now the theorem immediately follows taking L_{1} = x^{2/5}. This completes the proof.

References

[1] Edward A. Bender, Partitions of multisets, Discrete Math. 9 (1974), 301–311.

[2] Dominik Burek and Błażej Żmija, A new upper bound for numbers with the Lehmer property and its application to repunit numbers, Int. J. Number Theory 15 (2016), 1463–1468.

[3] E. R. Canfield, P. Erdős, and C. Pomerance, On a problem of Oppenheim concerning “Factorisatio Numerorum”, J. Number Theory 17 (1983), 1–28.

[4] G. L. Cohen and P. Hagis Jr., On the number of prime factors of n if φ(n) | (n − 1), Nieuw Arch. Wisk. (3) 28 (1980), 177–185.

[5] P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions, in Bruce C. Berndt, Harold G. Diamond, Heini Halberstam, and Adolf Hildebrand, eds., Analytic Number Theory, Proceedings of a Conference in Honor of Paul T. Bateman, Progr. Math., Vol. 85, Birkhäuser, 1990, pp. 165–204.

[6] José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, Integers 12 (2012), #A37.

[7] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th edition, Oxford University Press, 2008.

[8] D. H. Lehmer, On Euler’s totient function, Bull. Amer. Math. Soc. 38 (1932), 745–751.

[9] Florian Luca and Carl Pomerance, On composite integers n for which φ(n) | n − 1, Bol. Soc. Mat. Mexicana (3) 17 (2011), 13–21.

[10] Nathan McNew, Radically weakening the Lehmer and Carmichael conditions, Int. J. Number Theory 9 (2013), 1215–1224.

[11] Nathan McNew and Thomas Wright, Infinitude of k-Lehmer numbers which are not Carmichael, Int. J. Number Theory 12 (2016), 1863–1869.

[12] A. Oppenheim, On an arithmetic function II, J. London Math. Soc. 2 (1927), 123–130.

[13] Richard G. E. Pinch, Mathematics research page,

http://www.chalcedon.demon.co.uk/rgep/rcam.html.

[14] Carl Pomerance, On composites n for which φ(n) | (n − 1), II, Pacific J. Math. 69 (1977), 177–186.

[15] John Renze, Computational evidence for Lehmer’s totient conjecture,

https://library.wolfram.com/infocenter/MathSource/5483/.

2020 Mathematics Subject Classification: Primary 11A25; Secondary 11A05, 11N25. Keywords: Lehmer’s problem, Euler’s totient function, multiplicative partition.

(Concerned with sequences \underline{A001055}, \underline{A020555}, \underline{A033833}, \underline{A173703}, \underline{A337316}, and \underline{A338998}.)

Received November 24 2020; revised versions received November 25 2020; February 25 2021. Published in Journal of Integer Sequences, April 25 2021.

Return to Journal of Integer Sequences home page.