On Relatively Prime Subsets, Combinatorial Identities, and Diophantine Equations

Mohamed El Bachraoui Department of Mathematical Sciences United Arab Emirates University P.O. Box 17551 Al-Ain United Arab Emirates

                melbachraoui@uaeu.ac.ae

Abstract

Let n be a positive integer and let A be a nonempty finite set of positive integers. We say that A is relatively prime if gcd(A) = 1, and that A is relatively prime to n if gcd(A, n) = 1. In this work we count the number of nonempty subsets of A that are relatively prime and the number of nonempty subsets of A that are relatively prime to n. Related formulas are also obtained for the number of such subsets having some fixed cardinality. This extends previous work for the case where A is an interval of successive integers. As an application we give some identities involving Möbius and Mertens functions, which provide solutions to certain Diophantine equations.

1 Introduction

Throughout let n and α be positive integers and let A be a nonempty finite set of positive integers. Let #A = |A| denote the cardinality of A. We suppose in this paper that α ≤ |A|. Let μ be the Möbius function, let M(n) = ∑_{d=1}^{n} μ(d) be the Mertens function, and let ⌊x⌋ be the floor of x. If m and n are positive integers such that m ≤ n, then we let [m, n] = {m, m + 1, …, n}. The set A is called relatively prime if gcd(A) = 1 and it is called relatively prime to n if gcd(A ∪ {n}) = gcd(A, n) = 1.

Definition 1. Let

f(A) = #{X ⊆ A : X ≠ ∅ and gcd(X) = 1},
f_{α}(A) = #{X ⊆ A : #X = α and gcd(X) = 1},
Φ(A, n) = #{X ⊆ A : X ≠ ∅ and gcd(X, n) = 1},
Φ_{α}(A, n) = #{X ⊆ A : #X = α and gcd(X, n) = 1}.

Nathanson [5] introduced, among others, the functions f(n), f_{α}(n), Φ(n), and Φ_{α}(n) (in our terminology f([1, n]), f_{α}([1, n]), Φ([1, n], n), and Φ_{α}([1, n], n) respectively) and found exact formulas along with asymptotic estimates for each of these functions. Formulas for these functions along with asymptotic estimates are found in El Bachraoui [3] and Nathanson and Orosz [6] for A = [m, n] and in El Bachraoui [4] for A = [1, m]. Ayad and Kihel [1, 2] considered extensions to sets in arithmetic progression and obtained identities for these functions for A = [l, m] as consequences. Formulas connecting the functions Φ_{k}(n) and f_{k}(n) are found in Tang [7] and formulas for other related functions along with asymptotic estimates are given by Tóth [8]. An analysis of the functions f, f_{α}, Φ, and Φ_{α} obtained for different cases of the set A lead us to more general formulas for any nonempty finite set of positive integers. For the purpose of this work we give these functions for A = [l, m].

Theorem 2. We have

\begin{aligned}(a) f([l, m]) & = ∑_{d=1}^{m} μ(d)(2^{⌊ \frac{m}{d} ⌋−⌊ \frac{l−1}{d} ⌋} − 1), \\ (b) f_{α}([l, m]) & = ∑_{d=1}^{m} μ(d)\binom{⌊\frac{m}{d}⌋ − ⌊\frac{l−1}{d}⌋}{α}, \\ (c) Φ([l, m], n) & = ∑_{d|n} μ(d)2^{⌊ \frac{m}{d} ⌋−⌊ \frac{l−1}{d} ⌋}, \\ (d) ϕ_{α}([l, m], n) & = ∑_{d|n} μ(d)\binom{⌊\frac{m}{d}⌋ − ⌊\frac{l−1}{d}⌋}{α}. \end{aligned}

By way of example, using our formula for f(A) we will get that if gcd(m, n) = 1, then the following expression

∑_{d=1}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}

boils down to the much more simple expression ∑_{d=1}^{n} μ(d) = M(n), see Theorem 9 below. In terms of Diophantine equations, this means that the integer pair (2, 1) is a solution to

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 1 ,

if gcd(m, n) = 1, see Corollary 10(a). Related to this, an open question is whether or not other real or integer solutions exist for the previous equation.

2 Phi functions for integer sets

Theorem 3. We have

(a) Φ(A, n) = ∑_{d|n} μ(d)2^{∑_{a∈A}(⌊ \frac{a}{d} ⌋−⌊ \frac{a−1}{d} ⌋)}.

(b) Φ_{α}(A, n) = ∑_{d|n} μ(d)\binom{∑_{a∈A}(⌊\frac{a}{d}⌋ − ⌊\frac{a−1}{d}⌋)}{α}.

Proof. (a) We use induction on |A|. If A = {a} = [a, a], then by Theorem 2 (c)

Φ(A, n) = ∑_{d|n} μ(d)2^{⌊ \frac{a}{d} ⌋−⌊ \frac{a−1}{d} ⌋}.

Assume that A = {a_{1}, a_{2}, …, a_{k}} and that the identity holds for {a_{2}, …, a_{k}}. Then

Φ({a_{1}, …, a_{k}}, n) = Φ({a_{2}, …, a_{k}}, n) + Φ({a_{2}, …, a_{k}}, gcd(a_{1}, n))

= ∑_{d|n} μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} + ∑_{d|(a_{1},n)} μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}

= 2 ∑_{d|(a_{1},n)} μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} + ∑_{\begin{matrix}d|n \\ d∤a_{1} \end{matrix}}μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}

= ∑_{d|(a_{1},n)} μ(d)2^{⌊ \frac{a_{1}}{d} ⌋−⌊ \frac{a_{1}−1}{d} ⌋}2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}

+ ∑_{\begin{matrix}d|n \\ d∤a_{1} \end{matrix}}μ(d)2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}

= ∑_{d|(a_{1},n)} μ(d)2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} + ∑_{\begin{matrix}d|n \\ d∤a_{1} \end{matrix}}μ(d)2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}

= ∑_{d|n} μ(d)2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}.

(b) Similar. Corollary 4. Let l_{1}, l_{2}, …, l_{k} and m_{1}, m_{2}, …, m_{k} be nonnegative integers such that l_{i} < m_{i} for i = 1, 2, …, k and m_{i} ≤ l_{i+1} for i = 1, 2, …, k − 1. Then

(a) Φ([l_{1} + 1, m_{1}] ∪ [l_{2} + 1, m_{2}] ∪ … ∪ [l_{k} + 1, m_{k}], n) = ∑_{d|n} μ(d)2^{∑_{i=1}^{k}(⌊ \frac{m_{i}}{d} ⌋−⌊ \frac{l_{i}}{d} ⌋)}.

(b) Φ_{α}([l_{1} + 1, m_{1}] ∪ [l_{2} + 1, m_{2}] ∪ … ∪ [l_{k} + 1, m_{k}], n) = ∑_{d|n} μ(d)\binom{∑_{i=1}^{k}(⌊\frac{m_{i}}{d} ⌋ − ⌊\frac{l_{i}}{d} ⌋)}{α}.

Proof. Apply Theorem 3 to the set

A = {l_{1} + 1, l_{1} + 2, …, m_{1}, l_{2} + 1, l_{2} + 2, …, m_{2}, …, l_{k} + 1, l_{k} + 2, …, m_{k}}.

Corollary 5. If n ∈ A, then Φ(A, n) ≡ 0 mod 2.

Proof. Note first that

∑_{a∈A} (⌊\frac{a}{d}⌋ − ⌊\frac{a − 1}{d}⌋)

counts the number of multiples of d in the set A. So, if n ∈ A, then evidently ∑_{a∈A}(⌊\frac{a}{d}⌋ − ⌊\frac{a−1}{d}⌋) > 0 for all divisor d of n and thus the required congruence follows by Theorem 3(a).

3 Relatively prime subsets of integer sets

Theorem 6. We have

(a) f(A) = ∑_{d=1}^{sup A} μ(d) (2^{∑_{a∈A}(⌊ \frac{a}{d} ⌋−⌊ \frac{a−1}{d} ⌋)} − 1) .

(b) f_{α}(A) = ∑_{d=1}^{sup A} μ(d)\binom{∑_{a∈A}(⌊\frac{a}{d}⌋ − ⌊\frac{a−1}{d}⌋)}{α}.

Proof. (a) We use induction on |A|. If A = {a} = [a, a], then by Theorem 2 (a)

f(A) = ∑_{d=1}^{a} μ(d) (2^{⌊ \frac{a}{d} ⌋−⌊ \frac{a−1}{d} ⌋} − 1) .

Assume now that A = {a_{1}, a_{2}, …, a_{k}} and that the identity is true for {a_{2}, …, a_{k}}. Without loss of generality we may assume that a_{1} < sup A. Then, with the help of Theorem 3(a), we have

f({a_{1}, …, a_{k}}) =

= f({a_{2}, …, a_{k}}) + Φ({a_{2}, …, a_{k}}, a_{1}))
= ∑_{d=1}^{sup A} μ(d) (2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1) + ∑_{d|a_{1}} μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}
= ∑_{d|a_{1}} μ(d) (2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1) + ∑_{\begin{matrix}d=1 \\ d∤a_{1} \end{matrix}}^{sup A}μ(d) (2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1) + ∑_{d|a_{1}} μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}
= 2 ∑_{d|a_{1}} μ(d)2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − ∑_{d|a_{1}} μ(d) + ∑_{\begin{matrix}d=1 \\ d∤a_{1} \end{matrix}}^{sup A}μ(d) (2^{∑_{i=2}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1)
= ∑_{d|a_{1}} μ(d) (2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1) + ∑_{\begin{matrix}d=1 \\ d∤a_{1} \end{matrix}}^{sup A}μ(d) (2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1)
= ∑_{d=1}^{sup A} μ(d) (2^{∑_{i=1}^{k}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)} − 1) .

(b) Similar. Corollary 7. Let l_{1}, l_{2}, …, l_{k} and m_{1}, m_{2}, …, m_{k} be nonnegative integers such that l_{i} < m_{i} for i = 1, 2, …, k and m_{i} ≤ l_{i+1} for i = 1, 2, …, k − 1. Then

(a) f([l_{1} + 1, m_{1}] ∪ [l_{2} + 1, m_{2}] ∪ … ∪ [l_{k} + 1, m_{k}]) = ∑_{d=1}^{sup A} μ(d) (2^{∑_{i=1}^{k}(⌊ \frac{m_{i}}{d} ⌋−⌊ \frac{l_{i}}{d} ⌋)} − 1) .

(b) f_{α}([l_{1} + 1, m_{1}] ∪ [l_{2} + 1, m_{2}] ∪ … ∪ [l_{k} + 1, m_{k}], n) = ∑_{d=1}^{sup A} μ(d)\binom{∑_{i=1}^{k}(⌊\frac{m_{i}}{d} ⌋ − ⌊\frac{l_{i}}{d} ⌋)}{α}.

Proof. Apply Theorem 6 to the set A = {l_{1} + 1, l_{1} + 2, …, m_{1}, l_{2} + 1, l_{2} + 2, …, m_{2}, …, l_{k} + 1, l_{k} + 2, …, m_{k}}.

Alternatively, we have the following formulas for f(A) and f_{α}(A). Theorem 8. Let A = {a_{1}, a_{2}, …, a_{k}}, let τ be a permutation of {1, 2, …, k}, and let A_{τ(j)} = {a_{τ(1)}, a_{τ(2)}, …, a_{τ(j)}} for j = 1, 2, …, k. Then

(a) f(A) = ∑_{d|a_{τ(1)}} μ(d) + ∑_{j=2}^{k} ∑_{d|a_{τ(j)}} μ(d)2^{∑_{i=1}^{j−1}(⌊ \frac{a_{τ(i)}}{d} ⌋−⌊ \frac{a_{τ(i)}−1}{d} ⌋)}.

(b) f_{α}(A) = ∑_{j=1}^{k} ∑_{d|a_{τ(j)}} μ(d)\binom{∑_{i=1}^{j−1}(⌊\frac{a_{τ(i)}}{d} ⌋ − ⌊\frac{a_{τ(i)}−1}{d}⌋)}{α − 1}.

Proof. For simplicity we assume that τ is the identity permutation. As to part (a) we have with the help of Theorem 3

f({a_{1}, …, a_{k}}) = f({a_{1}, …, a_{k−1}}) + Φ({a_{1}, …, a_{k−1}}, a_{k})

= f({a_{1}}) + Φ({a_{1}}, a_{2}) + … + Φ({a_{1}, …, a_{k−1}}, a_{k})

= ∑_{d|a_{1}} μ(d) + ∑_{d|a_{2}} μ(d)2^{⌊\frac{a_{1}}{d} ⌋−⌊ \frac{a_{1}−1}{d}⌋}

+ … + ∑_{d|a_{k}} μ(d)2^{∑_{i=1}^{k−1}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)}

= ∑_{d|a_{1}} μ(d) + ∑_{j=2}^{k} ∑_{d|a_{j}} μ(d)2^{∑_{i=1}^{j−1}(⌊ \frac{a_{i}}{d} ⌋−⌊ \frac{a_{i}−1}{d} ⌋)},

where the third formula follows from Theorem 3. Part (b) follows similarly.

4 Combinatorial identities and Diophantine equations

We now give some identities involving Mertens function which provide solutions to a type of Diophantine equations.

Theorem 9. Let m and n be positive integers such that 1 < m < n. Then

∑_{d=1}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} = \begin{cases}M(n), if gcd(m, n) > 1; \\ 1 + M(n), if gcd(m, n) = 1. \end{cases}

Proof. If gcd(m, n) > 1, then clearly have f({m, n}) = 0. If 1 < m ≤ n and gcd(m, n) = 1, then clearly f({m, n}) = 1. On the other hand, by Theorem 6 (a) applied to the set {m, n} we have

\begin{aligned}f(\{m, n\}) & = ∑_{d=1}^{n} μ(d)(2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − 1) \\ & = ∑_{d=1}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − M(n). \end{aligned}

Combining the identities for f({m, n}) for the case gcd(m, n) > 1 gives

M(n) = ∑_{d=1}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}

and for the case 1 < m ≤ n and gcd(m, n) = 1 gives

1 + M(n) = ∑_{d=1}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}.

This completes the proof.

In terms of Diophantine equations Theorem 9 translates into the following.

Corollary 10. Let 1 < m < n be positive integers. Then (a) If gcd(m, n) = 1, then (2, 1) is a solution to the equation

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 1.

(b) If gcd(m, n) > 1, then (1, 2) and (2, 1) are solutions to the equation

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 0.

Proof. Immediate from Theorem 9.

Theorem 11. Let l, m, and n be integers such that 1 < l < m < n. Then

∑_{d=1}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋+⌊ \frac{l}{d} ⌋−⌊ \frac{l−1}{d} ⌋} =

4 + M(n), if gcd(l, m) = gcd(l, n) = gcd(m, n) = 1;

3 + M(n), if exactly two pairs from {l, m, n} are co-prime; 2 + M(n), if exactly one pair from {l, m, n} is co-prime; 1 + M(n), if no pair from {l, m, n} is co-prime and gcd(l, m, n) = 1; M(n), otherwise.

Proof. Suppose that 1 < l < m < n and gcd(l, m) = gcd(l, n) = gcd(m, n) = 1. Then the relatively prime subsets of {l, m, n} are

{l, m}, {l, n}, {m, n}, and {l, m, n},

implying that f({l, m, n}) = 4. Combining this with the formula for f({l, m, n}) obtained by using Theorem 6 (a) we get

∑_{d=1}^{n} μ(d)(2^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋+⌊ \frac{l}{d} ⌋−⌊ \frac{l−1}{d} ⌋} − 1) = 4,

which is equivalent to the first case of the desired identity. As to the second case, if exactly two pairs are co-prime, then f({l, m, n}) = 3 and the result follows from Theorem 6 (a). The remaining three cases follow similarly and the proof is completed.

In terms of Diophantine equations Theorem 11 means the following.

Corollary 12. Let l, m, n be integers such that 1 < l < m < n. Then

(a) If gcd(l, m) = gcd(l, n) = gcd(m, n) = 1, then (2, 1) is a solution to

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 4.

(b) If exactly two pairs from {l, m, n} are co-prime, then (2, 1) is a solution to

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 3.

(c) If exactly one pair from {l, m, n} is co-prime, then (2, 1) is a solution to

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 2.

(d) If no pair from {l, m, n} is co-prime and gcd(l, m, n) = 1, then (2, 1) is a solution to

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 1.

(e) Otherwise, the integer pairs (1, 2) and (2, 1) are solutions to

∑_{d=1}^{n} μ(d)(x^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋} − y^{⌊ \frac{n}{d} ⌋−⌊ \frac{n−1}{d} ⌋+⌊ \frac{m}{d} ⌋−⌊ \frac{m−1}{d} ⌋}) = 0.

Proof. Straightforward from Theorem 11.

We close the paper by some open questions which are suggested by our results.

Open Questions.

Question 1. Do the Diophantine equations in Corollary 10 and Corollary 12 have any other real solutions? Question 2. Do the Diophantine equations in Corollary 10 and Corollary 12 have any other integer solutions? Question 3. It is clear that any real pair (x, x) is a solution to the equation in part (b) of Corollary 10 and to the equation in part (e) of Corollary 12. These solutions might be called trivial. Is the number of non-trivial integer solutions to the equations in Corollary 10 and Corollary 12 finite?

5 Acknowledgments

The author is grateful to the referee for valuable comments and interesting suggestions.

References

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

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

   electronically at http://www.integers-ejcnt.org/vol9.html.

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

   http://www.integers-ejcnt.org/vol7.html.

[4] M. El Bachraoui, On the number of subsets of [1, m] relatively prime to n and asymptotic estimates, Integers 8 (1) (2008), A41. Available electronically at

   http://www.integers-ejcnt.org/vol8.html.

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

   http://www.integers-ejcnt.org/vol7.html.

[6] M. B. Nathanson and B. Orosz, Asymptotic estimates for phi functions for subsets of {m + 1, m + 2, …, n}, Integers 7 (2007), A54. Available electronically at

   http://www.integers-ejcnt.org/vol7.html.

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

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

   http://www.integers-ejcnt.org/vol10.html.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11B05, 11B75, 11D41. Keywords: phi function, relatively prime set, Mertens function, Möbius function, combinatorial identities, Diophantine equation.

Received September 23 2011; revised version received February 2 2012; March 14 2012. Published in Journal of Integer Sequences, March 25 2012.

Return to Journal of Integer Sequences home page.