ARITHMETIC PROGRESSIONS IN A UNIQUE FACTORIZATION DOMAIN

SUDHIR R. GHORPADE AND SAMRITH RAM

Abstract. Pillai showed that any sequence of consecutive integers with at most 16 terms possesses one term that is relatively prime to all the others. We give a new proof of a slight generalization of this result to arithmetic progressions of integers and further extend it to arithmetic progressions in unique factorization domains of characteristic zero.

1. Introduction

In an attempt to prove a conjecture that products of consecutive integers are never perfect powers, Pillai [16] (see also [19]), in the early 1940’s, considered the problem of finding sets of positive integers having the property that they possess an element that is relatively prime to all the rest. He showed that in any set of at most 16 consecutive integers there exists one that is relatively prime to the others. In addition, he proved that for 17 ≤ m ≤ 430, there exist infinitely many sets of m consecutive integers which possess no element that is relatively prime to all the rest. Pillai, in fact, believed that the latter result is true for all m ≥ 17, and this was soon confirmed by Brauer [2] and independently by Pillai himself [17, 18] using a result of Erdős [5, Theorem II]; for more recent proofs, one may refer to Evans [7], Harborth [11], and Eggleton [4]. In what follows, we shall refer to the former result as the Pillai Theorem and the latter as the Brauer-Pillai Theorem.

It is not difficult to show that the Pillai Theorem is applicable not only to sets of at most 16 consecutive integers, but also to arithmetic progressions of integers with at most 16 terms, and we will refer to this fact as the Generalized Pillai Theorem. While we have not found in the existing literature a proof of this fact (see, however, Remark 3.3), analogues of the Brauer-Pillai Theorem for arithmetic progressions are readily found, and we cite, in particular, the works of Evans [8], Ohtomo and Tamari [14], and

Date: March 12, 2012.

2010 Mathematics Subject Classification. Primary 11B25, 13F15; Secondary 11A05, 13A05.

Key words and phrases. Consecutive integers, arithmetic progressions, unique factorization domain, Bézout domain, GCD domain, decomposition number.

2 SUDHIR R. GHORPADE AND SAMRITH RAM

of Hajdu and Saradha [10]. Moreover, numerous extensions, analogues and generalizations of the Brauer-Pillai Theorem have been considered in the recent past; see, for example, Caro [3], Gassko [9], Saradha and Thangadurai [20], and also the works cited above. It may be remarked that all these extensions are in the setting of integers and use techniques from elementary or analytic number theory.

We consider in this paper an extension of the Generalized Pillai Theorem in a wider algebraic context. Thus, we ask, if a similar result holds for Gaussian integers, or more generally, for rings of integers of algebraic number fields of class number one, or even more generally, for arbitrary integral domains where the notion of GCD (and hence of two elements being relatively prime) makes sense. Our main result is an analogue of the Generalized Pillai Theorem for the so-called σ-atomic GCD domains of characteristic zero, and in particular, for arbitrary unique factorization domains of characteristic zero. This is achieved partly by introducing an invariant associated to an integral domain, called its decomposition number. It is then proved that if R is a UFD of characteristic zero with decomposition number δ_{R} and if N := min{16, 1 + δ_{R}}, then any arithmetic progression of at most N terms with the first term coprime to the common difference contains a term that is relatively prime to all the rest. It is also shown that N := min{16, 1 + δ_{R}} is the maximum possible number with this property. As a special case, one sees that the Generalized Pillai Theorem holds for the Gaussian integers with 16 replaced by 6. Our proof of the general result makes use of the corresponding result for integers. With this in view, and in a bid to make this paper self-contained, we include in Section 2 below a fairly short proof of the Generalized Pillai Theorem for arithmetic progressions of integers, which gives, in particular, a new proof of the Pillai Theorem. Some ring theoretic preliminaries and the notion of decomposition number are discussed in Section 3. The main result is proved in Section 4.

2. Arithmetic Progressions of Integers

Let us begin with some notations and terminology, which will be used in the remainder of this paper. Let R be an integral domain. For r ∈ R and S ⊆ R, we denote by M(r, S) the set {s ∈ S : r | s} of all multiples of r in S. For a, d ∈ R and a positive integer n, we denote by AP(a, d, n) the set {a, a + d, …, a + (n − 1)d} of elements of the arithmetic progression with n terms having a as its first term and d the common difference. Further, if R is a GCD domain (i.e. an integral domain in which any two elements have a

ARITHMETIC PROGRESSIONS IN A UNIQUE FACTORIZATION DOMAIN 3

greatest common divisor) and m, n are positive integers, then we shall write {a_{1}, a_{2}, …, a_{m}} ⊥ {b_{1}, b_{2}, …, b_{n}} to mean that gcd(a_{i}, b_{j}) = 1 for 1 ≤ i ≤ m and 1 ≤ j ≤ n. Here, as usual, gcd(a, b) denotes a greatest common divisor of a, b ∈ R, and although it is determined only up to multiplication by a unit, statements such as “gcd(a, b) = 1” or “gcd(a, b) divides c” have an unambiguous and obvious meaning, and we shall continue to use them. Of course if R = ℤ is the ring of integers, then gcd(a, b) is unique since we require it to be positive if a, b ∈ ℤ are not both zero and set gcd(0, 0) := 0. Also if R = ℤ and n is a positive integer, then ≤ will denote the componentwise partial order on ℤ^{n} so that for any a_{1}, …, a_{n}, b_{1}, …, b_{n} ∈ ℤ, (a_{1}, …, a_{n}) ≤ (b_{1}, …, b_{n}) ⟺ a_{i} ≤ b_{i} for all i = 1, …, n. Finally, for a finite set A, we denote by |A| the cardinality of A.

Theorem 2.1 (Generalized Pillai Theorem). Let a, d be coprime integers and let n be a positive integer ≤ 16. Then the arithmetic progression a, a + d, …, a + (n − 1)d contains a term that is relatively prime to all the others.

We first make an elementary observation and record a useful consequence thereof.

Lemma 2.2. If R is a GCD domain, a, d ∈ R are coprime and r, s are nonnegative integers, then

gcd(a + rd, a + sd) | (r − s).

Proof. Any common divisor of a+rd and a+sd divides both (a+rd)−(a+sd) and s(a + rd) − r(a + sd). Since gcd(a, d) = 1, the lemma follows. □

Corollary 2.3. If a, d are coprime integers and m is a positive integer, then

|M(m, AP(a, d, n))| ≤ ⌈n/m⌉

where ⌈x⌉ denotes the least integer ≥ x.

We now proceed to prove Theorem 2.1. For n = 1, the theorem is vacuously true. Let us first consider the case in which all terms of AP(a, d, n) are odd. The case where n = 2 is trivial. If n = 3, 4 or 5, then the term a + 2d is relatively prime to all the others. If n = 6, then one of a + 2d, a + 3d is not divisible by 3 and is relatively prime to all the other terms. If n = 7, 8, 9, 10 or 11, one of a + 4d, a + 5d, a + 6d is coprime to both 3 and 5 and consequently is relatively prime to all the other terms. If 12 ≤ n ≤ 16, some element in the set {a + id : 6 ≤ i ≤ 10} is coprime to 3, 5 and 7 and is relatively prime to all the others in AP(a, d, n). Thus Theorem 2.1 holds whenever all terms of AP(a, d, n) are odd, or equivalently, when d is even.

4 SUDHIR R. GHORPADE AND SAMRITH RAM

It remains to consider the case when terms in the progression are alternately even and odd. The case where n = 2 is trivial. If n = 3, the term a + d is relatively prime to the others. If n = 4 or 5, at least two terms in the progression are odd and one of those is not divisible by 3. This number is relatively prime to the others. To settle the remaining cases, the following two lemmas will be useful.

Lemma 2.4. Let k be an integer with 3 ≤ k ≤ 8. Suppose Theorem 2.1 holds for any coprime integers a, d with d odd and for n = 2k − 1. Then it also holds for any coprime integers a, d with d odd and for n = 2k.

Proof. Let a, d be coprime integers with d odd. Write a_{i} := a + (i − 1)d for i = 1, …, 2k and A := AP(a, d, 2k) = {a_{1}, …, a_{2k}}. Assume first that a_{1} is odd. Now A \ {a_{1}} = AP(a_{2}, d, 2k − 1) and hence there exists m ∈ ℤ with 2 ≤ m ≤ 2k such that a_{m} ⊥ A \ {a_{1}, a_{m}}. This implies that a_{m} ⊥ {1, …, m − 2}. Moreover, m is odd since both a_{1}, d are odd and k ≥ 3. Consequently, gcd(a_{1}, a_{m}) | (m − 1)/2. On the other hand, 1 ≤ (m − 1)/2 ≤ m − 2, since m ≥ 3. It follows that gcd(a_{m}, (m − 1)/2) = 1 and therefore gcd(a_{1}, a_{m}) = 1. As a result, a_{m} ⊥ A \ {a_{m}}. In case a_{1} is even, a_{2k} is odd and we use the same argument for AP(a_{2k}, −d, 2k). □

Lemma 2.5. Let k be an integer with 3 ≤ k ≤ 7. Suppose Theorem 2.1 holds for any odd coprime integers a, d and for n = 2k. Then it holds for any odd coprime integers a, d and for n = 2k + 1.

Proof. The proof is similar to that of Lemma 2.4. Let a, d be odd coprime integers. Write a_{i} = a+(i−1)d for i = 1, …, 2k+1 and A = AP(a, d, 2k+1). By the hypothesis, there exists m ∈ ℤ with 2 ≤ m ≤ 2k + 1 such that a_{m} ⊥ A \ {a_{1}, a_{m}}. This implies that a_{m} ⊥ {1, …, m − 2}. Moreover, m is odd, gcd(a_{1}, a_{m}) | (m − 1)/2, and (m − 1)/2 ≤ m − 2, since m ≥ 3. Thus gcd(a_{m}, a_{1}) = 1 and a_{m} ⊥ A \ {a_{m}}. □

In view of the two lemmas above and the discussion preceding it, it suffices to prove the theorem for coprime integers a, d with a even, d odd, and for odd integers n with 7 ≤ n < 16. Fix such a, d, n and let a_{i} := a+(i−1)d for i = 1, …, n and A := AP(a, d, n) = {a_{1}, …, a_{n}}. We now proceed by a case-by-case argument.

First, suppose n = 7. Let B := {a_{2}, a_{4}, a_{6}} = AP(a_{2}, 2d, 3). By Corollary 2.3, |M(3, B) ∪ M(5, B)| ≤ 2 < |B|. Hence it follows that there exists x ∈ B such that x ⊥ {2, 3, 5}. Consequently, x ⊥ A \ {x}.

ARITHMETIC PROGRESSIONS IN A UNIQUE FACTORIZATION DOMAIN 5

Next, suppose n = 9. Let B := A \ M(2, A) = AP(a_{2}, 2d, 4). By Corollary 2.3,

(|M(3, B)|, |M(5, B)|, |M(7, B)|) ≤ (2, 1, 1).

Since |B| = 4, if there is a strict inequality in one of the coordinates, then there is x ∈ B such that x ⊥ {2, 3, 5, 7} and consequently x ⊥ A \ {x}. If equality holds in all the coordinates, then |M(3, B)| = 2 and we must necessarily have M(3, B) = {a_{2}, a_{8}}. But then {a_{4}, a_{6}} ⊥ {2, 3} and the one among a_{4} and a_{6} that is coprime to 5 is relatively prime to all other elements in A.

For n = 11, let B := A \ M(2, A) = AP(a_{2}, 2d, 5). By Corollary 2.3,

(|M(3, B)|, |M(5, B)|, |M(7, B)|) ≤ (2, 1, 1).

Since 2 + 1 + 1 < 5 = |B|, there exists x ∈ B with x ⊥ {2, 3, 5, 7} and so x ⊥ A \ {x}.

We now consider the case n = 13. Let B := A \ M(2, A) = AP(a_{2}, 2d, 6). Then |B| = 6 and by Corollary 2.3,

(|M(3, B)|, |M(5, B)|, |M(7, B)|, |M(11, B)|) ≤ (2, 2, 1, 1).

If there is a strict inequality in one of the coordinates we are through. So suppose equality holds in all coordinates. This forces M(5, B) = {a_{2}, a_{12}}. So if we let B_{1} := {a_{4}, a_{6}, a_{8}}, then B_{1} ⊥ {2, 5} and by Corollary 2.3, (|M(3, B_{1})|, |M(7, B_{1})|) ≤ (1, 1). Thus there exists x ∈ B_{1} such that x ⊥ {2, 3, 5, 7} and hence x ⊥ A \ {x}.

Finally, suppose n = 15. Let B := A\(M(2, A)∪{a_{2}, a_{14}}) = AP(a_{4}, 2d, 5). Then |B| = 5 and by Corollary 2.3,

(|M(3, B)|, |M(5, B)|, |M(7, B)|, |M(11, B)|) ≤ (2, 1, 1, 1).

If there is a strict inequality in one of the coordinates or if

|M(3, B) ∪ M(5, B) ∪ M(7, B) ∪ M(11, B)| < 5,

then we are through. So suppose equality holds in all coordinates and the four sets M(j, B), j = 3, 5, 7, 11, are disjoint. Let B_{1} := {a_{2}, a_{14}}. Note that M(3, B_{1}) = ∅. If M(5, B_{1}) = ∅, then B_{1} ⊥ {2, 3, 5, 7, 11} and since |M(13, B_{1})| ≤ 1, some element of B_{1} is coprime to all the other elements in A. If |M(5, B_{1})| = 1, then |M(3, {a_{4}, a_{12}})| = |M(5, {a_{4}, a_{12}})| = 1. Consequently, there is x ∈ {a_{6}, a_{8}, a_{10}} such that 11 | x, and hence x ⊥ {2, 3, 5, 7}. It follows that x ⊥ A \ {x}. This completes the proof of Theorem 2.1.

Corollary 2.6 (Pillai). In any sequence of at most 16 consecutive integers, there exists an element that is relatively prime to all the others.

6 SUDHIR R. GHORPADE AND SAMRITH RAM

Proof. This is just the case d = 1 of Theorem 2.1. □

Recall that an integer is said to be a perfect power if it is of the form t^{r} where t and r are integers > 1.

Corollary 2.7. Suppose a, d are coprime positive integers and n is a positive integer ≤ 16 such that no term of AP(a, d, n) is a perfect power. Then the product ∏_{k=0}^{n−1} (a + kd) is not a perfect power.

Proof. The case n = 1 is trivial. If n ≥ 2, then by Theorem 2.1, there is a term x in AP(a, d, n) that is coprime to the other terms. If x > 1, then the desired result is clear since x is not a perfect power. In case x = 1, we must have a = 1 and so one can apply Theorem 2.1 to AP(a + d, d, n − 1). □

Remark 2.8. The hypothesis above that no term of AP(a, d, n) is a perfect power is crucial since one can find infinitely many arithmetic progressions (with the first term coprime to the common difference) with 3 terms each of which is a square. This follows from the fact that there are infinitely many rational points on the curve x^{2} + y^{2} = 2. For instance, {1, 5^{2}, 7^{2}}, {7^{2}, 13^{2}, 17^{2}} and {17^{2}, 53^{2}, 73^{2}}.

Remark 2.9. A remarkable theorem of Erdős and Selfridge [6] says that the product of two or more consecutive positive integers is never a perfect power.

Remark 2.10. As mentioned in the Introduction, for each n > 16 there exist blocks of n consecutive integers such that they contain no integer relatively prime to all the rest. We refer to Evans [7] for an elegant proof of this result.

3. GCD domains and Decomposition Numbers

The notion of a GCD domain was recalled in the Introduction. Let us also recall that an integral domain R is said to be a Bézout domain if every finitely generated ideal of R is principal, while it is said to be atomic if every nonzero nonunit in R factors into a product of irreducible elements. In analogy with the latter, we shall say that an integral domain R is σ-atomic if every nonzero nonunit in R is divisible by an irreducible element. Evidently, a unique factorization domain (UFD) is a σ-atomic (in fact, atomic) GCD domain. The following example shows that the converse is not true.

Example 3.1. Let R be the ring of entire functions, i.e., complex-valued holomorphic functions on ℂ. The units of R are precisely the entire functions

ARITHMETIC PROGRESSIONS IN A UNIQUE FACTORIZATION DOMAIN 7

with no zeros in ℂ and the irreducible elements are given, up to multiplication by units, by the linear polynomials. Thus it is readily seen that R is a σ-atomic domain. Moreover, R is also a GCD domain, and in fact, a Bézout domain, thanks to a result of Helmer [12] (which was, incidentally, published in the same year as Pillai [16]). On the other hand, since there do exist entire functions with infinitely many zeros (e.g., sin z), we see that R is not a UFD. More generally, if R′ is any subring of R such that R′ strictly contains the subring of R consisting of the polynomial functions, then R′ is a σ-atomic GCD domain that is not a UFD. To generate more examples, it suffices to observe that if S is a σ-atomic GCD domain that is not a UFD, then the polynomial ring S[X] is also a σ-atomic GCD domain that is not a UFD; moreover, it is not difficult to see that S[X] is neither Noetherian nor Bèzout.

In the sequel, the following version of Chinese Remainder Theorem will turn out to be useful. A proof when R = ℤ can be found in the book of Ore [15, §10–3] and it extends easily to the case when R is any Bézout domain, or more generally, a GCD domain where the moduli satisfy a Bézout hypothesis such as (3.1) below.

Lemma 3.2 (Generalized Chinese Remainder Theorem). Let R be a GCD domain, m be a positive integer, and let u_{i}, v_{i} ∈ R with v_{i} ≠ 0 for i = 1, …, m. Assume that

(3.1)  gcd (v_{i}, v_{j}) ∈ Rv_{i} + Rv_{j} for 1 ≤ i, j ≤ m.

Then the system z ≡ u_{i} (mod v_{i}), i = 1, …, m, of m congruences possesses a solution in R if and only if gcd(v_{i}, v_{j}) | (u_{i} − u_{j}) for 1 ≤ i, j ≤ m.

Remark 3.3. As an application of Lemma 3.2, let us show that the Pillai Theorem (Corollary 2.6) and the Generalized Pillai Theorem (Theorem 2.1) can be deduced from each other. To prove the nontrivial implication, let a, d be coprime integers and n be a positive integer ≤ 16. Write a_{i} = a+(i−1)d for i = 1, …, n. By Lemma 2.2, gcd(a_{i}, a_{j}) | i − j for 1 ≤ i, j ≤ n. Hence by Lemma 3.2, there is z ∈ ℤ such that a_{i} | z − i for i = 1, …, n. Now by Corollary 2.6, there is k ∈ {1, …, n} such that z − k is relatively prime to z − j for all j = 1, …, n with j ≠ k. Consequently, a_{k} is relatively prime to a_{j} for all j ≠ k.

It is not difficult to show that in a GCD domain, irreducible elements are always prime. In what follows, prime elements of an arbitrary integral domain may simply be referred to as primes, and this terminology should

8 SUDHIR R. GHORPADE AND SAMRITH RAM

not be confused with prime ideals. Also, following the standard conventions of number theory, we will use the term rational prime to mean a (positive) prime number in ℤ. Now here is a definition that will play a crucial role in the proof of our main theorem.

Definition 3.4. Let ℜ be an integral domain with multiplicative identity 1_{ℜ}. The decomposition number of ℜ, denoted by δ_{ℜ}, is the smallest rational prime p such that p · 1_{ℜ} is divisible by at least two distinct (i.e., up to multiplication by units) prime elements in ℜ. If no prime in ℤ is divisible by two distinct primes in ℜ, then we define δ_{ℜ} to be ∞.

It seems worthwhile to illustrate this notion with several examples.

Examples 3.5. (i) Clearly, δ_{ℤ} = ∞. Also, if K is a field, then δ_{K} = ∞. (ii) If A is an integral domain, then δ_{A[[X]]} = δ_{A[X]} = δ_{A}. (iii) If R is the ring of entire functions, then δ_{R} = ∞. (iv) Suppose ℜ = ℤ[α] is a UFD for some complex number α satisfying a

monic irreducible polynomial f(X) ∈ ℤ[X]. Then using a well-known result of Kummer-Dedekind, we see that δ_{ℜ} is the smallest rational prime p such that the image of f(X) in ℤ/pℤ[X] is divisible by two distinct irreducible polynomials in ℤ/pℤ[X]. The next two examples are special cases of this.

(v) Let K = ℚ(\sqrt{m}) for some squarefree m ∈ ℤ such that ℜ = O_{K} is a UFD. If m ≡ 1(mod 8), then δ_{ℜ} = 2 and for other values of m, δ_{ℜ} is the smallest rational prime p such that p is odd and (\frac{m}{p}) = 1. (Here (\frac{·}{·}) denotes the Legendre symbol). In particular, δ_{ℤ[i]} = 5.

(vi) Suppose ζ_{m} is a primitive m-th root of unity such that ℜ = ℤ[ζ_{m}] is a UFD. (The precise values of m for which ℤ[ζ_{m}] is a UFD are known; cf. [13]). For any rational prime p, let p^{v_{p}(m)} be the highest power of p dividing m and let ℓ(m, p) := m/p^{v_{p}(m)}. Then from [1, Theorem 2], we see that δ_{ℜ} is the smallest rational prime p for which ℓ(m, p) > 1 and p is not a primitive root modulo ℓ(m, p).

4. Arithmetic Progressions in GCD domains

For an integral domain ℜ, we shall denote by ℤ_{ℜ} the prime subring of ℜ. In case ℜ is of characteristic zero, ℤ_{ℜ} can be identified with ℤ.

Theorem 4.1. Let ℜ be a σ-atomic GCD domain of characteristic 0. Then we have the following:

ARITHMETIC PROGRESSIONS IN A UNIQUE FACTORIZATION DOMAIN 9

(i) If n is a positive integer ≤ min {16, 1 + δ_{ℜ}}, then for any coprime a, d ∈ ℜ, the arithmetic progression AP(a, d, n) contains a term that is relatively prime to all the others.

(ii) Assume that no prime of ℤ_{ℜ} is a unit in ℜ. Then for each integer n with n > min {16, 1 + δ_{ℜ}}, there exists an arithmetic progression AP(a, d, n) in ℜ, where a, d ∈ ℜ are coprime, such that none of its terms is relatively prime to all the others.

Proof. (i) Assume, on the contrary, that n ≤ min {16, 1 + δ_{ℜ}} and that there exists an arithmetic progression a_{1}, …, a_{n} in ℜ with gcd (a_{1}, a_{2}) = 1 such that no term is relatively prime to the rest. Let d = a_{2} − a_{1}. For each i there exists a j_{i} such that a_{i} is not coprime to a_{j_{i}}. Then there exists a prime P_{i} dividing gcd (a_{i}, a_{j_{i}}). Let π be the product of the distinct primes in {P_{1}, …, P_{n}}, say

π = P_{i_{1}}P_{i_{2}} ⋯ P_{i_{k}}.

Let r_{i} = gcd (π, a_{i}). Note that no r_{i} is relatively prime to all the r_{j}(j ≠ i). For any prime P ∈ ℜ let I_{P} = {i : P | r_{i}}. Suppose

⋃_{j=1}^{k}{I_{P_{i_{j}}} } = {I_{Q_{1}}, I_{Q_{2}}, ⋯, I_{Q_{l}}}.

where each Q_{m} is one of the P_{i_{j}}. Now define

s_{i} = gcd (r_{i}, Q_{1} ⋯ Q_{l}) (1 ≤ i ≤ n).

Again note that no s_{i} is relatively prime to all the s_{j}(j ≠ i). By the choice of the s_{i}, it follows that if Q_{s} ≠ Q_{t}, then

|{i : Q_{s} | s_{i}}| ≥ 2 and {i : Q_{s} | s_{i}} ≠ {i : Q_{t} | s_{i}}.

Note that a_{i} ≡ 0 (mod s_{i}). If P is a prime dividing some s_{l}, then P also divides some s_{m}(l ≠ m). Then P | (l − m)1_{ℜ}. If p ∈ ℤ is the positive prime such that P ℜ ∩ ℤ_{ℜ} = pℤ_{ℜ}, then it follows that p | (l − m). Thus p ≤ n − 1 ≤ δ_{ℜ}. This implies that each s_{i}(1 ≤ i ≤ n) is a product of primes each of which lies over p · 1_{ℜ} for some positive prime p ∈ ℤ not exceeding δ_{ℜ}. Also, any prime P lying over δ_{ℜ} · 1_{ℜ} can appear in the factorization of some s_{m} only if n = δ_{ℜ} + 1 and in this case P necessarily divides both s_{1} and s_{n} and no other s_{i}. Also, in this case no other prime Q ∈ ℜ lying over δ_{ℜ} ·1_{ℜ} can divide s_{1} or s_{n} (since {i : P | s_{i}} ≠ {i : Q | s_{i}}). Now, the system

z ≡ −(i − 1)d (mod s_{i}) 1 ≤ i ≤ n

possesses a solution, namely z = a_{1} in ℜ. This implies that

gcd (s_{i}, s_{j}) | (i − j)d · 1_{ℜ} 1 ≤ i, j ≤ n.

10 SUDHIR R. GHORPADE AND SAMRITH RAM

Also note that gcd (s_{i}, d) = 1 for all i (otherwise the fact that the first term is coprime to the common difference is contradicted). Thus we have

(4.1)  gcd (s_{i}, s_{j}) | (i − j) · 1_{ℜ} 1 ≤ i, j ≤ n.

For each i let t_{i} ∈ ℤ denote the unique positive integer such that s_{i}ℜ∩ℤ_{ℜ} = t_{i}ℤ_{ℜ}. Let t_{ij} = gcd (t_{i}, t_{j}) and s_{ij} = gcd (s_{i}, s_{j}). Then t_{ij} ∈ t_{i}ℤ_{ℜ} + t_{j}ℤ_{ℜ} and consequently

(4.2)  s_{ij} ∈ ℜs_{i} + ℜs_{j}.

From (4.1) and (4.2) together with Lemma 3.2, it follows that the system

z ≡ (1 − i)1_{ℜ} (mod s_{i}), i = 1, …, n,

possesses a solution in ℜ. By the choice of s_{i} and t_{i} it is easily seen that

s_{ij}ℜ ∩ ℤ_{ℜ} = t_{ij}ℤ_{ℜ}.

Consequently

gcd (t_{i}, t_{j}) | (i − j) for 1 ≤ i, j ≤ n

and so by Lemma 3.2, the system

z ≡ 1 − i (mod t_{i}), i = 1, …, n,

possesses a solution, say x, in ℤ. Note that no t_{i} is relatively prime to all the others. Now x, x+1, …, x+n−1 is a sequence of n consecutive integers such that none of them is relatively prime to all the rest. Hence by Corollary 2.6, n > 16, which is a contradiction. This proves (i).

(ii) If n > 16, then by Remark 2.10 there exists an arithmetic progression AP(a, d, n) in ℤ (and hence in ℤ_{ℜ}) such that none of its terms is relatively prime to all the others. Since no prime in ℤ_{ℜ} is a unit in ℜ we are through. So we only need to consider progressions where 1+δ_{ℜ} < n < 17. For δ_{ℜ} < 17 let P, Q be distinct primes in ℜ dividing δ_{ℜ}1_{ℜ}. Let z ∈ ℜ be a solution of the system

z ≡ 0 (mod 2 · 3 · 5 · 7 · 11 · 13 · \frac{P}{δ_{ℜ}} )
z + 1_{ℜ} ≡ 0 (mod Q).

Then for 1 + δ_{ℜ} < n < 17, we claim that the progression z, z + 1_{ℜ}, …, z + (n − 1)1_{ℜ} contains no term relatively prime to all the others. Indeed, z and z +1_{ℜ} share a common factor with z +δ_{ℜ}1_{ℜ} and z +(δ_{ℜ} +1)1_{ℜ} respectively, whereas all other terms in the progression share a common factor with either z or z + 1_{ℜ}. This completes the proof of Theorem 4.1. □

ARITHMETIC PROGRESSIONS IN A UNIQUE FACTORIZATION DOMAIN 11

Remark 4.2. In part (i) of Theorem 4.1, the hypothesis that ℜ is σ-atomic is crucial. For example, if ℜ is the ring 𝔸 of all algebraic integers (all complex numbers integral over ℤ), then δ_{𝔸} = ∞ since there are no prime elements in 𝔸. However, the progression

\frac{\sqrt{17} + 3}{2}, \frac{\sqrt{17} + 5}{2}, \frac{\sqrt{17} + 7}{2}, \frac{\sqrt{17} + 9}{2}

contains no element coprime to the others. Also, in part (ii) of Theorem 4.1, the assumption that no prime in ℤ is a unit in ℜ is necessary. For example, if ℜ is a field, then every arithmetic progression in ℜ with at least one nonzero term contains a term that is relatively prime to all the others.

Remark 4.3. Note that only values of δ_{ℜ} ≤ 13 can affect the permissible values of n such that AP(a, d, n) contains a term coprime to the others. For the purposes of the above theorem it is unnecessary to determine δ_{ℜ} if it is known to be greater than 13 (this of course includes the case δ_{ℜ} = ∞).

Definition 4.4. An element of an integral domain R is said to be a perfect power if it can be expressed in the form t^{r} where t is a nonzero, non-unit in R and r is a positive integer > 1.

Corollary 4.5. Let ℜ be a UFD of characteristic 0 and a, d ∈ ℜ be coprime. If n is a positive integer ≤ min {16, 1 + δ_{ℜ}} and if AP(a, d, n) contains no units and no perfect powers, then the product ∏_{k=0}^{n−1} (a + kd) is not a perfect power.

Proof. If some term of AP(a, d, n) is zero, then so is the product and 0 is not a perfect power, by definition. Otherwise, the result follows readily from Theorem 4.1. □

References

[1] G. Bachman, The decomposition of a rational prime ideal in cyclotomic fields, Amer. Math. Monthly 73 (1966), 494–497.

[2] A. Brauer, On a property of k consecutive integers, Bull. Amer. Math. Soc. 47 (1941), 328–331.

[3] Y. Caro, On a division property of consecutive integers, Israel J. Math. 33 (1979), no. 1, 32–36.

[4] R. B. Eggleton, Common factors of integers: a graphic view, Discrete Math. 65 (1987), no. 2, 141–147.

[5] P. Erdős, On the difference of consecutive primes, Quart. J. Math. 6 (1935), 124–

12 SUDHIR R. GHORPADE AND SAMRITH RAM

[6] P. Erdős and J. L. Selfridge, The product of consecutive integers is never a power, Illinois J. Math. 19 (1975), 292–301.

[7] R. J. Evans, Mathematical Notes: On Blocks of N Consecutive Integers, Amer. Math. Monthly 76 (1969), no. 1, 48–49.

[8] R. J. Evans, On N consecutive integers in an arithmetic progression, Acta Sci. Math. (Szeged) 33 (1972), 295–296.

[9] I. Gassko, Stapled sequences and stapling coverings of natural numbers, Electron. J. Combin. 3 (1996), no. 1, Research Paper 33, approx. 20 pp. (electronic).

[10] L. Hajdu and N. Saradha, On a problem of Pillai and its generalizations, Acta Arith. 144 (2010), 323-347.

[11] H. Harborth, Eine Eigenschaft aufeinanderfolgender Zahlen, Arch. Math. (Basel) 21 (1970), 50–51.

[12] O. Helmer, Divisibility properties of integral functions, Duke Math. J. 6 (1940), 345–356.

[13] J. Myron Masley and H. L. Montgomery, Cyclotomic fields with unique factorization, J. Reine Angew. Math. 286/287 (1976), 248–256.

[14] M. Ohtomo and F. Tamari, On relative prime number in a sequence of positive integers, J. Statist. Plann. Inference 106 (2002), no. 1-2, 509–515.

[15] Oystein Ore, Number Theory and Its History, McGraw-Hill Book Company, Inc., New York, 1948.

[16] S. S. Pillai, On m consecutive integers I, Proc. Indian Acad. Sci., Sect. A. 11 (1940), 6–12.

[17] S. S. Pillai, On m consecutive integers III, Proc. Indian Acad. Sci., Sect. A. 13 (1941), 530–533.

[18] S. S. Pillai, On m consecutive integers IV, Bull. Calcutta Math. Soc. 36 (1944), 99–101.

[19] S. S. Pillai, Collected works of S. Sivasankaranarayana Plliai, Eds. R. Balasubramanian and R. Thangadurai, Collected Works Series, no. 1, Ramanujan Mathematical Society, Mysore, 2010.

[20] N. Saradha and R. Thangadurai, Pillai’s problem on consecutive integers, Number theory and applications, Hindustan Book Agency, New Delhi, 2009, pp. 175–188.

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: srg@math.iitb.ac.in

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: samrith@gmail.com