On the Number of Subsets Relatively Prime to an Integer

Mohamed Ayad Laboratoire de Mathématiques Pures et Appliquées Université du Littoral F-62228 Calais France

                  ayad@lmpa.univ-littoral.fr

Omar Kihel Department of Mathematics Brock University St. Catharines, Ontario L2S 3A1 Canada

                       okihel@brocku.ca

Abstract Fix a positive integer and a finite set whose elements are in arithmetic progression. We give a formula for the number of nonempty subsets of this set that are coprime to the given integer. A similar formula is given when we restrict our attention to the subsets having the same fixed cardinality. These formulas generalize previous results of El Bachraoui.

1 Introduction

A nonempty subset A of {1, 2, …, n} is said to be relatively prime if gcd(A) = 1. Nathanson [4] defined 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. Nathanson [4] defined Φ(n) to be the number of nonempty subsets A of the set {1, 2, …, n} such that gcd(A) is relatively prime to n and, for integer k ≥ 1, Φ_{k}(n) to be the number of subsets A of the set {1, 2, …, n} such that gcd(A) is relatively prime to n and card(A) = k.

He obtained explicit formulas for these functions and deduced asymptotic estimates. These functions have been generalized by El Bachraoui [3] to subsets A ∈ {m + 1, m + 2, …, n} where m is any nonnegative integer, and then by Ayad and Kihel [1] to subsets of the set {a, a + b, …, a + (n − 1)b} where a and b are any integers.

El Bachraoui [2] defined for any given positive integers l ≤ m ≤ n, Φ([l, m], n) to be the number of nonempty subsets of {l, l + 1, …, m} which are relatively prime to n and Φ_{k}([l, m], n) to be the number of such subsets of cardinality k. He found formulas for these functions when l = 1 [2]. In this paper, we generalize these functions and obtain El Bachraoui’s result as a particular case.

2 Phi functions for {1, 2, …, m}

Let k and l ≤ m ≤ n be positive integers. Let ⌊x⌋ denote the greatest integer less than or equal to x, and μ(n) the Möbius function. El Bachraoui [2] defined Φ([l, m], n) to be the number of nonempty subsets of {l, l + 1, …, m} which are relatively prime to n and Φ_{k}([l, m], n) to be the number of such subsets of cardinality k. He proved the following formulas [2]:

Φ([1, m], n) = ∑_{d|n} μ(d)2^{[ \frac{m}{d}]}  (1)

and

Φ_{k}([1, m], n) = ∑_{d|n} μ(d) ( \begin{matrix}[\frac{m}{d}] \\ k \end{matrix} ) .  (2)

In his proof of Eqs. (1) and (2), El Bachraoui [2] used the Möbius inversion formula and its extension to functions of several variables. The case m = n in (1), was proved by Nathanson [4].

3 Phi functions for {a, a + b, …, a + (m − 1)b}

It is natural to ask whether one can generalize the formulas obtained by El Bachraoui [2] to a set A = {a, a + b, …, a + (m − 1)b}, where a, b, and m are positive integers. Let Φ^{(a,b)}(m, n) be the number of nonempty subsets of {a, a + b, …, a + (m − 1)b} which are relatively prime to n and Φ_{k}([l, m], n) to be the number of such subsets of cardinality k. To state our main theorem, we need the following lemma, which is proved in [1]:

Lemma 1. For an integer d ≥ 1, and for nonzero integers a and b such that gcd(a, b) = 1, let A_{d} = {x = a + ib for i = 0, …, (m − 1)| d | x}. Then

(i) If gcd (b, d) ≠ 1, then |A_{d}| = 0.

(ii) If gcd (b, d) = 1, then |A_{d}| = ⌊\frac{m}{d}⌋ + ε_{d}, where

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

Theorem 2.

Φ^{(a,b)}(m, n) = ∑ ; \begin{matrix}d|n \\ gcd(b, d) = 1 \end{matrix} μ(d) (2^{⌊ \frac{m}{d} ⌋+ϵ_{d}} − 1)  (4)

and

Φ_{k}^{(a,b)}(m, n) = ∑ ; \begin{matrix}d|n \\ gcd(b, d) = 1 \end{matrix} μ(d) ( \begin{matrix}⌊\frac{m}{d}⌋ + ϵ_{d} \\ k \end{matrix} ) ,  (5)

where ϵ_{d} is the function defined in Lemma 1.

Proof. Let A_{d} = {x = a+ib for i = 0, …, (m−1)| d | x}, and P(A_{d}) = {the nonempty subsets of A_{d}}.

It is easy to see that Φ^{(a,b)}(m, n) = (2^{m} − 1) − | ⋃ ; \begin{matrix}p prime \\ p | n \end{matrix} P(A_{p})|. Clearly, if p_{1}, …, p_{t} are

distinct primes, then

|⋂_{i=1}^{t} P(A_{p_{i}})| = |P(A_{∏_{i=1}^{t} p_{i}})| .

Thus, using the principle of inclusion-exclusion, one obtains from above that

Φ^{(a,b)}(m, n) = \begin{matrix}∑ \\ d|n \end{matrix} μ(d)|P(A_{d})|.

It was proved in Lemma 1, that if gcd(b, d) ≠ 1, then |A_{d}| = 0 and if gcd(b, d) = 1, then

|A_{d}| = (⌊\frac{m}{d}⌋ + ε_{d}). Hence

Φ^{(a,b)}(m, n) = ∑ ; \begin{matrix}d|n \\ gcd(b, d) = 1 \end{matrix} μ(d) (2^{[ \frac{m}{d}]+ϵ_{d}} − 1) .

The proof for Eq. (5) is similar.

Theorem 3 in [2] can be deduced from Theorem 2 above as the particular case where a = b = 1. We prove the following.

Corollary 3. (a) Φ([1, m], n) = Φ^{(1,1)}(m, n) and

(b) Φ_{k}([l, m], n) = Φ_{k}^{(1,1)}(m, n) .

Proof. It is not difficult to prove that when a = b = 1 in Lemma 1, ϵ_{d} = 0. Using Theorem 2, and the well-known equality ∑_{d|n} μ(d) = 0, one obtains that

Φ^{(1,1)}(m, n) = ∑_{d|n} μ(d) (2^{⌊ \frac{m}{d} ⌋} − 1) = \begin{matrix}∑ \\ d|n \end{matrix} μ(d)2^{⌊ \frac{m}{d} ⌋} = Φ([1, m], n)  (6)

and

Φ_{k}^{(1,1)}(n) = ∑_{d|n} μ(d) ( \begin{matrix}⌊\frac{m}{d}⌋ \\ k \end{matrix} ) = Φ_{k}([1, m], n).  (7)

Example 4. Using Theorem 2, one can obtain asymptotic estimates and generalize Corollary 4 proved by El Bachraoui [2].

References

[1] M. Ayad and O. Kihel, On relatively prime sets, submitted.

[2] M. El Bachraoui, On the number of subsets of [1, m] relatively prime to n and asymptotic estimates, Integers 8 (2008), A41, 5 pp. (electronic).

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

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

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

2000 Mathematics Subject Classification: Primary 05A15. Keywords: relatively prime subset, Euler phi function.

Received October 22 2008; revised version received December 13 2008. Published in Journal of Integer Sequences, December 13 2008.

Return to Journal of Integer Sequences home page.