The Number of Relatively Prime Subsets of a Finite Union of Sets of Consecutive Integers

Mohamed Ayad

Laboratoire de Mathématiques Pures et Appliquées

Université du Littoral

F-62228 Calais

France

Ayad@lmpa.univ-littoral.fr

Vincenzo Coia Department of Statistics

University of British Columbia

Vancouver, BC V6T 1Z4

Canada

vincen.coia@stat.ubc.ca

Omar Kihel Department of Mathematics

Brock University St. Catharines, ON L2S 3A1

Canada

okihel@brocku.ca

Abstract

Let A be a finite union of disjoint sets of consecutive integers and let n be a positive integer. We give a formula for the number of relatively prime subsets (resp., relatively prime subsets of cardinality k) of A, which generalizes results of Nathanson, El Bachraoui and others. We give as well similar formulas for the number of subsets with gcd coprime to n.

1 Introduction

A nonempty set S of integers is said to be relatively prime if gcd (S) = 1, where gcd (S) denotes the greatest common divisor of the elements of S. Nathanson [10] defines f (n) to be the number of relatively prime subsets of {1, 2, …, n} and, for k ≥ 1, f_{k} (n) to be the number of relatively prime subsets of {1, 2, …, n} of cardinality k. By analogy with Euler’s phi function ϕ (n) that counts the number of positive integers a in the set {1, 2, …, n} such that gcd (a, n) = 1, Nathanson [10] defines Φ (n) to be the number of nonempty subsets S of the set {1, 2, …, n} such that gcd (S) is relatively prime to n and, for integer k ≥ 1, Φ_{k} (n) to be the number of subsets S of the set {1, 2, …, n} such that gcd(S) is relatively prime to n and |S| = k. He obtains explicit formulas for these four functions and deduces asymptotic estimates.

For simplicity, we use a more general notation than Nathanson [10]. For a nonempty set of integers S, we define

• f (S) = |{H ⊆ S : gcd (H) = 1, H ≠ ∅}| as the number of nonempty relatively prime subsets of S;

• f_{k} (S) = |{H ⊆ S : gcd (H) = 1, |H| = k}| as the number of relatively prime subsets of S of cardinality k;

• Φ (S, n) = |{H ⊆ S : gcd (H ∪ {n}) = 1, H ≠ ∅}| as the number of nonempty subsets of S with gcd relatively prime to integer n;

• Φ_{k} (S, n) = |{H ⊆ S : gcd (H ∪ {n}) = 1, |H| = k}| as the number of subsets of S of cardinality k and with gcd relatively prime to integer n.

Further, we define [a, b]_{ℤ} = [a, b] ∩ ℤ = {a, a + 1, …, b} for integers a < b as the set of consecutive integers from a to b, inclusive.

El Bachraoui [4] and Nathanson and Orosz [11] generalize the results of Nathanson [10] to subsets of [ℓ, m]_{ℤ} for integers 0 ≤ ℓ < m, and prove Theorem 1.

Theorem 1. For non-negative integers ℓ < m and k ≥ 1, using the notation f (ℓ, m) = f ([ℓ, m]_{ℤ}) and f_{k} (ℓ, m) = f_{k} ([ℓ, m]_{ℤ}) of El Bachraoui [4] and Nathanson and Orosz [11] we have

f (ℓ, m) = ∑_{d=1}^{m} μ (d) (2^{⌊^{\frac{m}{d}}⌋−⌊\frac{ℓ}{d}⌋} − 1)  (1)

and

f_{k} (ℓ, m) = ∑_{d=1}^{m} μ (d) \binom{⌊m/d⌋ − ⌊ℓ/d⌋}{k},  (2)

where μ is the Möbius function.

For brevity, define the arithmetic sequence A_{n}^{(a,b)} = {a, a + b, …, a + (n − 1)b} for positive integers n, a, and b. Ayad and Kihel [1] generalize Theorem 1 to obtain Theorem 2.

Theorem 2. For all positive integers n, a, and b, with gcd (a, b) = 1, using the notation f^{(a,b)} (n) = f (A_{n}^{(a,b)}) and f_{k}^{(a,b)} (n) = f_{k} (A_{n}^{(a,b)}) of Ayad and Kihel [1], we have

f^{(a,b)} (n) = ∑_{\begin{matrix}d=1 \\ gcd(b,d)=1 \end{matrix}}^{a+(n−1)b} μ (d) (2^{⌊^{\frac{n}{d}}⌋+ε_{d}} − 1)  (3)

and

f_{k}^{(a,b)} (n) = ∑_{\begin{matrix}d=1 \\ gcd(b,d)=1 \end{matrix}}^{a+(n−1)b} μ (d) \binom{⌊\frac{n}{d}⌋ + ε_{d}}{k},  (4)

where

ε_{d} = \begin{cases}0, & if d | n; \\ 1, & if d ∤ n and (−ab^{−1}) mod d ∈ \{⌊\frac{n}{d}⌋ d, …, n − 1\}; \\ 0, & otherwise. \end{cases}  (5)

El Bachraoui [6] extends Theorem 1 to the union of two sets of consecutive integers, to obtain Theorem 3.

Theorem 3. For nonnegative integers ℓ_{1} < m_{1} < ℓ_{2} < m_{2} and for k ≥ 1,

f ([ℓ_{1}, m_{1}]_{ℤ} ∪ [ℓ_{2}, m_{2}]_{ℤ}) = ∑_{d=1}^{m_{2}} μ (d) (2^{⌊^{\frac{m_{1}}{d}} ⌋+⌊\frac{m_{2}}{d} ⌋−⌊\frac{ℓ_{1}−1}{d}⌋−⌊\frac{ℓ_{2}−1}{d}⌋} − 1)  (6)

and

f_{k} ([ℓ_{1}, m_{1}]_{ℤ} ∪ [ℓ_{2}, m_{2}]_{ℤ}) = ∑_{d=1}^{m_{2}} μ (d) \binom{⌊\frac{m_{1}}{d} ⌋ + ⌊\frac{m_{2}}{d} ⌋ − ⌊\frac{ℓ_{1}−1}{d}⌋ − ⌊\frac{ℓ_{2}−1}{d}⌋}{k}.  (7)

We now switch our attention to analogous results for functions Φ and Φ_{k}. For the consecutive integers case, El Bachraoui [4] and Nathanson and Orosz [11] prove Theorem 4.

Theorem 4. For non-negative integers ℓ < m and k ≥ 1, using the notation Φ (ℓ, m) = Φ ([ℓ, m]_{ℤ} , m) and Φ_{k} (ℓ, m) = Φ_{k} ([ℓ, m]_{ℤ} , m) of El Bachraoui [4] and Nathanson and Orosz [11] we have

Φ (ℓ, m) = ∑_{d|m} μ (d) 2^{(\frac{m}{d} −⌊\frac{ℓ}{d}⌋)}  (8)

and

Φ_{k} (ℓ, m) = ∑_{d|m} μ (d) \binom{\frac{m}{d} − ⌊\frac{ℓ}{d}⌋}{k}.  (9)

Ayad and Kihel [1] generalize Theorem 4 to obtain Theorem 5.

Theorem 5. For nonnegative integers a, b, and n, with gcd (a, b) = 1, using the notation Φ^{(a,b)} (n) = Φ (A_{n}^{(a,b)}, n) and Φ_{k}^{(a,b)} (n) = Φ_{k} (A_{n}^{(a,b)}, n) of Ayad and Kihel [1] we have

Φ^{(a,b)} (n) = ∑_{\begin{matrix}d|n \\ gcd(b,d)=1 \end{matrix}} μ (d) (2^{\frac{n}{d}} − 1)  (10)

and

Φ_{k}^{(a,b)} (n) = ∑_{\begin{matrix}d|n \\ gcd(b,d)=1 \end{matrix}} μ (d) \binom{\frac{n}{d}}{k}.  (11)

El Bachraoui and Salim [9] extend Theorem 4 to the union of two sets of consecutive integers, to obtain Theorem 6.

Theorem 6. For nonnegative integers ℓ_{1} < m_{1} < ℓ_{2} < m_{2} and for k ≥ 1,

Φ ([ℓ_{1}, m_{1}]_{ℤ} ∪ [ℓ_{2}, m_{2}]_{ℤ} , n) = ∑_{d|n} μ (d) 2^{⌊^{\frac{m_{1}}{d}} ⌋+⌊\frac{m_{2}}{d} ⌋−⌊\frac{ℓ_{1}−1}{d}⌋−⌊\frac{ℓ_{2}−1}{d}⌋}  (12)

and

Φ_{k} ([ℓ_{1}, m_{1}]_{ℤ} ∪ [ℓ_{2}, m_{2}]_{ℤ} , n) = ∑_{d|n} μ (d) \binom{⌊\frac{m_{1}}{d} ⌋ + ⌊\frac{m_{2}}{d} ⌋ − ⌊\frac{ℓ_{1}−1}{d}⌋ − ⌊\frac{ℓ_{2}−1}{d}⌋}{k}.  (13)

In Section 2, we extend Theorems 3 and 6 to the union of any finite number of disjoint sets of consecutive integers. The approach we take is simple and much different from the approach of El Bachraoui [6] and El Bachraoui and Salim [9] for the union of two sets. Several authors [2, 3, 12, 7, 13, 14, 5] discuss other properties and generalizations.

2 Finite union of disjoint sets of consecutive integers

For positive integers ℓ_{i} ≤ m_{i} for i = 1, …, r, denote A^{(i)} = [ℓ_{i}, m_{i}]_{ℤ} for brevity and assume A^{(i)} ∩ A^{(j)} = ∅ for i ≠ j. Consider the union

A = r ; ⋃_{i=1}A^{(i)}.  (14)

El Bachraoui [6] derives equations for f (A) and f_{k} (A) for r = 2, as in Theorem 3. We extend this to any r ∈ ℕ in Theorem 8, but first we need Lemma 7. Also, throughout this section, for a set of integers S we denote P (S) = {H ⊆ S : H ≠ ∅} and P_{k} (S) = {H ⊆ S : |H| = k}.

Lemma 7. Let A_{d} = {x ∈ A : d | x} be all the multiples of d found in A, where A is defined in equation (14). Then,

|A_{d}| = r ; ∑_{i=1} (⌊\frac{m_{i}}{d} ⌋ − ⌊\frac{ℓ_{i} − 1}{d}⌋) .

Proof. For i = 1, …, r, let A_{d}^{(i)} = {x ∈ A^{(i)} : d | x}, M_{d}^{(i)} = {x ∈ [0, m_{i}]_{ℤ} : d | x}, and L_{d}^{(i)} =

{x ∈ [0, ℓ_{i} − 1]_{ℤ} : d | x}. Clearly, we have |A_{d}^{(i)}| = |M_{d}^{(i)}| − |L_{d}^{(i)}|. But, we simply have

|M_{d}^{(i)}| = ⌊\frac{m_{i}}{d} ⌋ and |L_{d}^{(i)}| = ⌊\frac{ℓ_{i}−1}{d}⌋. So,

|A_{d}^{(i)}| = ⌊\frac{m_{i}}{d} ⌋ − ⌊\frac{ℓ_{i} − 1}{d}⌋ .

Now, since A_{d} = r ; ⋃_{i=1}A_{d}^{(i)} and since A_{d}^{(i)} ∩ A_{d}^{(j)} = ∅ for i ≠ j, we have |A_{d}| = r ; ∑_{i=1} |A_{d}^{(i)}| which

completes the proof.

Theorem 8. For A defined in equation (14), we have

f(A) = max\{m_{1},...,m_{r}\} ; ∑_{d=1}μ (d) (2^{^{r ; ∑_{i=1}}(⌊^{\frac{m_{i}}{d}} ⌋−⌊\frac{ℓ_{i}−1}{d}⌋)} − 1);  (15)

f_{k}(A) = max\{m_{1},...,m_{r}\} ; ∑_{d=1}μ (d) \binom{r ; ∑_{i=1} (⌊\frac{m_{i}}{d} ⌋ − ⌊\frac{ℓ_{i}−1}{d}⌋)}{k}.  (16)

Proof. We begin by proving equation (15). From the total amount of nonempty subsets of A, remove those subsets that are not relatively prime:

f (A) = |P (A)| − | ⋃_{p prime}P (A_{p})| .

Using inclusion-exclusion and the same principle as in the proof of Ayad and Kihel [1, Theorem 5], we obtain

f (A) = max{m_{1},...,m_{r}} ; ∑_{d=1}μ (d) (2^{|A_{d}|} − 1) .

Applying Lemma (7), we obtain equation (15).

To prove equation (16), from the total amount of subsets of A with cardinality k, remove those subsets that are not relatively prime:

f_{k} (A) = |P_{k} (A)| − | ⋃_{p prime}P_{k} (A_{p})| .

Using inclusion-exclusion and the same principle as in the proof of Ayad and Kihel [1, Theorem 5], we obtain

f_{k}(A) = max\{m_{1},...,m_{r}\} ; ∑_{d=1}μ (d) \binom{|A_{d}|}{k}.

Applying Lemma (7), we obtain equation (16).

Similarly, we now extend Theorem 6.

Theorem 9. Define A as in equation (14). Then for any integer k ≥ 1,

Φ (A, n) = ∑_{d|n}μ (d) (2^{^{r ; ∑_{i=1}}(⌊^{\frac{m_{i}}{d}} ⌋−⌊\frac{ℓ_{i}−1}{d}⌋)} − 1);  (17)

Φ_{k} (A, n) = ∑_{d|n}μ (d) \binom{r ; ∑_{i=1} (⌊\frac{m_{i}}{d} ⌋ − ⌊\frac{ℓ_{i}−1}{d}⌋)}{k}.  (18)

Proof. We begin by proving equation (17). Notice that

Φ (A, n) = |P (A)| − | ⋃_{\begin{matrix}p prime \\ p|n \end{matrix}} P (A_{p})| .

As in the proof of Theorem 8, we have

Φ (A, n) = ∑_{d|n}μ (d) (2^{|A_{d}|} − 1) .

Applying Lemma 7 proves equation (17).

To prove equation (18), notice that

Φ_{k} (A, n) = |P_{k} (A)| − | ⋃_{\begin{matrix}p prime \\ p|n \end{matrix}} P_{k} (A_{p})| .

As in the proof of Theorem 8, we have

Φ_{k} (A, n) = ∑_{d|n}μ (d) \binom{|A_{d}|}{k}.

Applying Lemma 7 proves equation (18).

3 Aknowledgements

The authors would like to thank the anonymous referees for several helpful comments. The research of the third author is patially supported by NSERC.

References

[1] M. Ayad and O. Kihel, On relatively prime sets, Integers 9 (2009), 343–352.

[2] M. Ayad and O. Kihel, The number of relatively prime subsets of {1, 2, …, n}, Integers 9 (2009), 163–166.

[3] M. Ayad and O. Kihel, On the number of subsets relatively prime to an integer, J. Integer Seq. 11 (2008), Article 08.5.5.

[4] M. El Bachraoui, The number of relatively prime subsets and phi functions for {m, m+ 1, …, n}, Integers 7 (2007), #A43.

[5] M. El Bachraoui, On the number of subsets of [1, M] relatively prime to N and asymptotic estimates, Integers 8 (2008), #A41.

[6] M. El Bachraoui, Combinatorial identities involving Mertens function through relatively prime subjects, J. Comb. Number Theory 2 (2010), 181–188.

[7] M. El Bachraoui, On relatively prime subsets, combinatorial identities, and Diophantine equations, J. Integer Seq. 15 (2012), Article 12.3.6.

[8] M. El Bachraoui, On relatively prime subject and supersets, Integers 10 (2010), 565– 574.

[9] M. El Bachraoui and M. Salim, Combinatorial identities involving Möbius function through relatively prime subjects, J. Integer Seq. 13 (2010), Article 10.8.6.

[10] M. B. Nathanson, Affine invariants, relatively prime sets, and a phi function for subsets of {1, 2, …, n}, Integers 7 (2007), #A1.

[11] M. B. Nathanson and B. Orosz, Asymptotic estimates for phi functions for subsets of {M + 1, M + 2, …, N}, Integers 7 (2007), #A54.

[12] T. Shonhiwa, On relatively prime sets counting functions, Integers 10 (2010), 465–476.

[13] M. Tang, Relatively prime sets and a phi function for subsets of {1, 2, …, n}, J. Integer Seq. 13 (2010), Article 10.7.6.

[14] L. Tóth, On the number of certain relatively prime subsets of {1, 2, …, n}, Integers 10 (2010), 407–421.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11B05, 11B75, 11D41. Keywords: phi function, relatively prime set, combinatorial identity.

Received November 10 2011; revised versions received November 11 2011; June 10 2013; September 17 2013; January 27 2014. Published in Journal of Integer Sequences, February 16 2014.

Return to Journal of Integer Sequences home page.