When the Large Divisors of a Natural Number Are in Arithmetic Progression

Hùng Vi{ê \atop .}t Chu

Department of Mathematics University of Illinois at Urbana-Champaign Champaign, IL 61820 USA

                     hungchu2@illinois.edu

Abstract Iannucci considered the positive divisors of a natural number n that do not exceed the square root of n and found all numbers whose such divisors are in arithmetic progression. Continuing the work, we define large divisors to be divisors at least \sqrt{n} and find all numbers whose large divisors are in arithmetic progression. The asymptotic formula for the count of these numbers not larger than x is observed to be \frac{x log log x}{log x}.

1 Introduction

For a natural number n, let L_{n} denote the set of positive divisors of n that are at least \sqrt{n} and strictly smaller than n; that is,

L_{n} := \{d : d|n, \sqrt{n} ≤ d < n\}.

Also, define

L′_{n} := \{d : d|n, \sqrt{n} ≤ d ≤ n\}.

We call L′_{n} the set of large divisors of n. Clearly, we have |L′_{n}| = |L_{n}| + 1. In this paper, we will determine the set of all natural numbers n such that either L_{n} or L′_{n} forms an arithmetic progression. Since L_{n} ⊂ L′_{n}, if L′_{n} forms an arithmetic progression, then so does L_{n}. Hence, we will first focus our attention on L_{n} and find all n such that

L_{n} = {d, d + a, d + 2a, …, d + (k − 1)a} for some natural numbers d, a, and k. Note that L_{n} can be empty and in that case, L_{n} vacuously forms an arithmetic progression. Let |L_{n}| = k ≥ 0.

Our work is a companion to a paper of Iannucci [3], who defined small divisors of n to be divisors not exceeding \sqrt{n} and found all natural numbers whose small divisors are in arithmetic progression. For previous work on divisors in or not in arithmetic progression, see [1, 6] and on small divisors, see [2, 4].

As usual, we have the divisor-counting function

τ(n) := ∑_{d|n} 1.

Since τ(n) is multiplicative, for the k distinct primes p_{1} < p_{2} < ⋯ < p_{k} and natural numbers a_{1}, a_{2}, …, a_{k}, we have

τ(p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}}) = (a_{1} + 1)(a_{2} + 1) ⋯ (a_{k} + 1).  (1)

If n = bc and b ≤ c, then b ≤ \sqrt{n} ≤ c; hence

τ(n) = \begin{cases}2|L′_{n}|, & if n is not a square; \\ 2|L′_{n}| − 1, & if n is a square \end{cases} = \begin{cases}2|L_{n}| + 2, & if n is not a square; \\ 2|L_{n}| + 1, & if n is a square. \end{cases} (2)

Theorem 1. Let n be a natural number. If numbers in L_{n} are in arithmetic progression, then one of the following holds:

(i) n = 1, and hence L_{n} = ∅. (ii) n = p for some prime p, and hence L_{n} = ∅. (iii) n = p^{2} for some prime p, and hence L_{n} = {p}. (iv) n = p^{3} for some prime p, and hence L_{n} = {p^{2}}.

(v) n = pq for some primes p < q, and hence L_{n} = {q}. (vi) n = p^{4} for some prime p, and hence L_{n} = {p^{2}, p^{3}}. (vii) n = p^{5} for some prime p, and hence L_{n} = {p^{3}, p^{4}}. (viii) n = p^{2}q for some primes p < q, and hence L_{n} = {p^{2}, pq} or L_{n} = {q, pq}. (ix) n = pq^{2} for some primes p < q, and hence L_{n} = {pq, q^{2}}.

(x) n = pqr for some primes p < q < r, pq < r and p = \frac{1}{2}(q + 1), and hence L_{n} = {r, rp, rq}.

(xi) n = p^{3}q for some primes p > q and q = \frac{1}{2}(p + 1), and hence L_{n} = \{p^{2}, p^{2}q, p^{3}\}.

To prove Theorem 1, we first find all forms of n when |L_{n}| = k ≤ 3 by case analysis, then show that k cannot be larger than 3. To find all n such that L′_{n} forms an arithmetic progression, we need only to check the 11 forms in Theorem 1. It is straightforward to prove the following corollary, so we omit the proof.

Corollary 2. Let n be a natural number. If numbers in L′_{n} are in arithmetic progression, then one of the following holds:

(i) n = 1, and hence L′_{n} = {1}.

(ii) n = p, and hence L′_{n} = {p}.

(iii) n = p^{2} for some prime p, and hence L′_{n} = {p, p^{2}}.

(iv) n = p^{3} for some prime p, and hence L′_{n} = {p^{2}, p^{3}}.

(v) n = pq for some primes p < q, and hence L′_{n} = {q, pq}.

2 Small cases of |L_{n}|

Assuming L_{n} is in arithmetic progression, we fully characterize n when |L_{n}| ≤ 3 and prove that |L_{n}| ≠ 4.

Lemma 3. If L_{n} forms an arithmetic progression and k ≤ 3, then one of the items in Theorem 1 is true.

Proof. We consider four cases corresponding to each 0 ≤ k ≤ 3.

Case 1: If k = 0, then by (2), we have τ(n) ∈ {1, 2}. If τ(n) = 1, then n = 1. If τ(n) = 2, then n = p for some prime p. Hence, L_{n} = ∅. This corresponds to items (i) and (ii) of the theorem.

Case 2: If k = 1, then by (2), we have τ(n) ∈ {3, 4}.

If τ(n) = 3, then by (1), we have n = p^{2} for some prime p, and hence L_{n} = {p}. This corresponds to item (iii) of the theorem.

If τ(n) = 4, then by (1), we have n = p^{3} for some prime p or n = pq for some primes p < q. For the former, we get L_{n} = {p^{2}} and for the latter, we get L_{n} = {q}, corresponding to items (iv) and (v) of the theorem.

Case 3: If k = 2, then by (2), we have τ(n) ∈ {5, 6}.

If τ(n) = 5, then by (1), we have n = p^{4} for some prime p, and hence L_{n} = {p^{2}, p^{3}}. This corresponds to item (vi).

If τ(n) = 6, then by (1), we have n = p^{5} for some prime p or n = p^{2}q or pq^{2} for some primes p < q.

If n = p^{5}, then L_{n} = {p^{3}, p^{4}}.

If n = p^{2}q for some primes p < q < p^{2}, then L_{n} = {p^{2}, pq}. If n = p^{2}q for some primes p^{2} < q, we get L_{n} = {q, pq}.

If n = pq^{2} for some primes p < q, then L_{n} = {pq.q^{2}}.

These correspond to items (vii), (viii), (ix).

Case 4: If k = 3, then by (2), we have τ(n) ∈ {7, 8}.

If τ(n) = 7, then by (1), we get n = p^{6} for some prime p. Then L_{n} = {p^{3}, p^{4}, p^{5}}, which is impossible since p^{5} − p^{4} ≠ p^{4} − p^{3}.

If τ(n) = 8, then by (1), we get n = pqr for some distinct primes p, q, r or p^{3}q for some distinct primes p, q.

If n = pqr, we may assume that p < q < r. Two subcases are either r > pq or r < pq.

r > pq: We have L_{n} = {r, pr, qr} and so, qr − pr = pr − r, which implies that p = \frac{1}{2}(q + 1). This is item (x).

r < pq: We have L_{n} = {pq, pr, qr} and so, qr − pr = pr − pq, which implies that p = \frac{qr}{2r−q}. So, either (2r − q)|q or (2r − q)|r. However, both are impossible since 2r − q > r > q.

If n = p^{3}q, two subcases are either p < q or p > q.

p < q: If p < q < p^{3}, then L_{n} = {p^{3}, pq, p^{2}q}. Either p^{2}q − pq = pq − p^{3} or p^{2}q − p^{3} = p^{3} − pq. It is easy to see that both cases are impossible. If q > p^{3}, then L_{n} = {q, pq, p^{2}q}. Since p^{2}q − pq = pq − q, we get p^{2} = 2p − 1, which implies that p = 1, a contradiction.

p > q: L_{n} = \{p^{2}, p^{2}q, p^{3}\}. So, p^{3} − p^{2}q = p^{2}q − p^{2}. Then q = \frac{1}{2}(p + 1). This is item (xi).

Lemma 4. Our set L_{n} cannot have exactly 4 elements.

Proof. We prove this by contradiction. Suppose that |L_{n}| = 4. By (2), we have τ(n) ∈ {9, 10}.

If τ(n) = 9, then (1) implies that n = p^{8} for some prime p or n = p^{2}q^{2} for some primes p < q.

If n = p^{8}, then L_{n} = {p^{4}, p^{5}, p^{6}, p^{7}}, which cannot form an arithmetic progression.

If n = p^{2}q^{2} for p < q, then L_{n} = {pq, p^{2}q, q^{2}, pq^{2}}. So, pq^{2} + pq = p^{2}q + q^{2}, which implies that p = q, a contradiction.

If τ(n) = 10, either n = p^{9} for some prime p or n = pq^{4} for distinct primes p, q.

If n = p^{9}, then L_{n} = {p^{5}, p^{6}, p^{7}, p^{8}}, which cannot form an arithmetic progression.

If n = pq^{4}, we have four subcases.

p < q: L_{n} = {pq^{2}, q^{3}, pq^{3}, q^{4}}, so pq^{2} +q^{4} = q^{3} +pq^{3}, which implies that p = q, a contradiction. q < p < q^{2}: L_{n} = {q^{3}, pq^{2}, q^{4}, pq^{3}}, so q^{3} + pq^{3} = pq^{2} + q^{4}, which implies that p = q, a contradiction. q^{2} < p < q^{4}: L_{n} = {pq, q^{4}, pq^{2}, pq^{3}}. Either pq^{3} + pq = pq^{2} + q^{4} or pq^{3} + q^{4} = pq + pq^{2}. The former gives q = 1, while the latter gives p = −\frac{q^{3}}{q^{2}−q−1}. Both pose a contradiction. q^{4} < p: L_{n} = {p, pq, pq^{2}, pq^{3}}, so p+pq^{3} = pq +pq^{2}, which implies that q = 1, a contradiction.

Therefore, |L_{n}| ≠ 4.

3 Proof of Theorem 1

By Lemmas 3 and 4, to prove Theorem 1, it suffices to prove that |L_{n}| ≤ 4.

Proof of Theorem 1. We prove this by contradiction. Suppose that k = |L_{n}| ≥ 5. Recall that

L_{n} = {d, d + a, d + 2a, …, d + (k − 1)a}

for some natural numbers d and a. Let gcd(d, a) = ℓ. Write d = ℓk_{1} and a = ℓk_{2}. Clearly, gcd(k_{1}, k_{2}) = 1, so there exist integers s, t such that sk_{1} + tk_{2} = 1.

Let

M = lcm (d, d + a, d + 2a, …, d + (k − 1)a);

that is, M denotes the least common multiple of all numbers in L_{n}. Write

M = lcm (ℓk_{1}, ℓk_{1} + ℓk_{2}, ℓk_{1} + 2ℓk_{2}, …, ℓk_{1} + (k − 1)ℓk_{2})
= ℓ · lcm (k_{1}, k_{1} + k_{2}, k_{1} + 2k_{2}, …, k_{1} + (k − 1)k_{2}).

We claim that gcd(k_{1} + (k − 2)k_{2}, k_{1} + (k − 1)k_{2}) = 1. Indeed, let

x = k_{1} + (k − 1)k_{2}
y = k_{1} + (k − 2)k_{2}.

We have

k_{2} = x − y
k_{1} = x − (k − 1)k_{2} = x − (k − 1)(x − y).

Because sk_{1} + tk_{2} = 1, we have

s(x − (k − 1)(x − y)) + t(x − y) = 1.

So,

(t + s − s(k − 1))x + ((k − 1)s − t)y = 1,

which implies that gcd(x, y) = 1. Hence,

N = ℓ(k_{1} + (k − 2)k_{2})(k_{1} + (k − 1)k_{2}) = ℓ · lcm (k_{1} + (k − 2)k_{2}, k_{1} + (k − 1)k_{2}) divides M.

Because N divides M and M divides n, we know that N divides n. Clearly, N > ℓ(k_{1} + (k − 1)k_{2}) = d + (k − 1)a ≥ \sqrt{n}. Because N ∉ L_{n}, we get N = n. So, ℓ(k_{1} + (k − 3)k_{2}) divides N. Hence,

k_{1} + (k − 3)k_{2} divides (k_{1} + (k − 2)k_{2})(k_{1} + (k − 1)k_{2}).

Using the same argument as above, we know that gcd(k_{1} + (k − 3)k_{2}, k_{1} + (k − 2)k_{2}) = 1. So,

k_{1} + (k − 3)k_{2} divides k_{1} + (k − 1)k_{2}.

Write k_{1} + (k − 1)k_{2} = u(k_{1} + (k − 3)k_{2}) for some integer u ≥ 2. Simplifying the equation, we get

\frac{3u − 1}{u − 1} = \frac{k_{1} + kk_{2}}{k_{2}} = \frac{k_{1}}{k_{2}} + k > 5.

So, u < 2. This contradicts that u ≥ 2. Therefore, it must be that |L_{n}| < 5, as desired.

Remark 5. We can estimate how often a natural number n not larger than x > 0 has its large divisors form an arithmetic progression. Let f(x) be the function counting such numbers not larger than x.

The number of n not larger than x that is either of form p, p^{2}, or p^{3} for a prime p is asymptotic to

∑_{i=1}^{3} π(x^{1/i}) ∼ ∑_{i=1}^{3} \frac{ix^{1/i}}{log x}.

By a result of Landau [5, §56], the number of n ≤ x of the form pq for primes p < q is asymptotic to

\frac{x log log x}{log x}.

Combined with Corollary 2, we know that

f(x) ∼ \frac{x log log x}{log x},

which is similar to the asymptotic formula for the case of small divisors [3].

References

[1] W. Banks, J. Friedlander, and F. Luca, Integers without divisors from a fixed arithmetic progression, Forum Math. 20 (2008), 1005–1037.

[2] D. Bruijn, N. Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskd. 23 (1951), 191–193.

[3] D. E. Iannucci, When the small divisors of a natural number are in arithmetic progression, Integers 18 (2018).

[4] D. E. Iannucci, On sums of the small divisors of a natural number, preprint, 2018.

   Available at https://arxiv.org/abs/1910.11835.

[5] E. Landau, Handbuch der Lehre von der Vorteilung der Primzahlen, B. G. Teubner, 1909.

[6] P. Varbanek and P. Zarzycki, Divisors of the Gaussian integers in an arithmetic progression, J. Number Theory 33 (1989), 152–169.

2010 Mathematics Subject Classification: Primary 11B25. Keywords: divisor, arithmetic progression.

Received January 29 2020; revised version received May 10 2020; May 12 2020. Published in Journal of Integer Sequences, June 9 2020.

Return to Journal of Integer Sequences home page.