<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf On Relatively Prime Subsets, Combinatorial \\
\vskip .1in Identities, and Diophantine Equations
}
\vskip 1cm
\large
Mohamed El Bachraoui\\
Department of Mathematical Sciences\\
United Arab Emirates University\\
P.O. Box 17551 \\
Al-Ain\\
United Arab Emirates\\
\href{mailto:echraoui@uaeu.ac.ae}{\tt melbachraoui@uaeu.ac.ae} \\
\end{center}

\vskip .2 in

  \begin{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\"obius and Mertens functions, which
  provide solutions to certain Diophantine equations.
  \end{abstract}


 \section{Introduction}
 Throughout let $n$ and $\alpha$ 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 $\alpha \leq |A|$.
 Let $\mu$ be the M\"obius function, let $M(n)=\sum_{d=1}^{n} \mu(d)$ be the Mertens function, and let
 $\lfloor x \rfloor$ be the floor of $x$. If $m$ and $n$ are positive integers such that $m\leq n$,
 then we let $[m,n]=\{m,m+1,\ldots,n\}$.
 \noindent
  The set $A$ is called \emph{relatively prime} if $\gcd(A) = 1$ and it is called
 \emph{relatively prime to $n$} if $\gcd(A\cup \{n\}) = \gcd(A,n) = 1$.
 \begin{definition}
  Let
  \[
  \begin{split}
  f(A) &amp;= \# \{X\subseteq A:\ X\not=
  \emptyset\ \text{and\ } \gcd(X) = 1 \}, \\
  f_{\alpha} (A) &amp;= \# \{X\subseteq A:\ \# X=
  \alpha \ \text{and\ } \gcd(X) = 1 \}, \\
  \Phi(A,n) &amp;= \# \{X\subseteq A:\ X\not=
  \emptyset\ \text{and\ } \gcd(X,n) = 1 \}, \\
  \Phi_{\alpha} (A,n) &amp;= \# \{X\subseteq A:\ \# X=
  \alpha \ \text{and\ } \gcd(X,n) = 1 \}.
  \end{split}
  \]
 \end{definition}
 Nathanson \cite{Nathanson} introduced, among others, the functions $f(n)$, $f_{\alpha}(n)$, $\Phi(n)$, and $\Phi_{\alpha}(n)$
 (in our terminology $f([1,n])$, $f_{\alpha}([1,n])$, $\Phi([1,n],n)$, and $\Phi_{\alpha}([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~\cite{ElBachraoui1} and Nathanson~and~Orosz~\cite{Nathanson-Orosz} for $A= [m,n]$
  and in El Bachraoui~\cite{ElBachraoui2} for $A=[1,m]$.
 %
 Ayad and Kihel \cite{Ayad-Kihel1, Ayad-Kihel2} considered extensions to sets in arithmetic progression and obtained
 identities for these functions for $A=[l,m]$ as consequences.
 Formulas connecting the functions $\Phi_k(n)$ and $f_k(n)$ are found in Tang~\cite{Tang} and formulas
 for other related functions along with asymptotic estimates are given by
 T\'oth~\cite{Toth}.
 An analysis of the functions $f$, $f_{\alpha}$, $\Phi$, and $\Phi_{\alpha}$ 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]$.
 \begin{theorem} \label{relprime-interval} %\emph{(\cite{Ayad-Kihel1, Ayad-Kihel2})}
 We have
 \[
 \begin{split}
 (a)\quad f([l,m]) &amp;= \sum_{d=1}^{m}\mu(d)(2^{\lfloor\frac{m}{d}\rfloor - \lfloor\frac{l-1}{d}\rfloor}-1),\\
 (b)\quad f_{\alpha}([l,m]) &amp;= \sum_{d=1}^{m}\mu(d)\binom{\lfloor\frac{m}{d}\rfloor - \lfloor\frac{l-1}{d}\rfloor}{\alpha}, \\
 (c)\quad \Phi([l,m],n) &amp;= \sum_{d|n} \mu(d)2^{\lfloor\frac{m}{d}\rfloor - \lfloor\frac{l-1}{d}\rfloor}, \\
 (d)\quad \phi_{\alpha}([l,m],n) &amp;= \sum_{d|n} \mu(d)\binom{\lfloor\frac{m}{d}\rfloor - \lfloor\frac{l-1}{d}\rfloor}{\alpha}.
 \end{split}
 \]
 \end{theorem}
 By way of example, using our formula for $f(A)$ we will get that if $\gcd(m,n)=1$, then the following expression
 \[
 \sum_{d=1}^n \mu(d)
  2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor}
 \]
 boils down to the much more simple expression $\sum_{d=1}^n \mu(d) = M(n)$, see Theorem~\ref{Mertens-m,n} below.
 In terms of Diophantine equations, this means that the integer pair $(2,1)$ is a solution to
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 1\ ,
 \]
 if $\gcd(m,n)=1$, see Corollary~\ref{corol1}(a). Related to this, an open question is whether or not other real or integer
 solutions exist for the previous equation.
  \section{Phi functions for integer sets} \label{sec:function-phi}
 \begin{theorem} \label{main1}
 We have
 \[ (a)\quad
  \Phi(A,n)= \sum_{d|n}\mu(d) 2^{\sum_{a\in A}(\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor)}.
 \]
 \[ (b)\quad
  \Phi_{\alpha}(A,n)= \sum_{d|n}\mu(d) \binom{\sum_{a\in A}(\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor)}{\alpha}.
 \]
 \end{theorem}
 \begin{proof}
 (a)
  We use
  induction on $|A|$. If $A=\{a \}=[a,a]$, then by Theorem \ref{relprime-interval} (c)
  \[ \Phi(A,n) =\sum_{d|n} \mu(d) 2^{\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor}.
  \]
  Assume that $A=\{a_1,a_2,\ldots,a_k \}$ and that the identity holds for $\{a_2,\ldots,a_k\}$. Then
  \[
  \begin{split}
  \Phi(\{a_1,\ldots,a_k\},n)
  &amp;=
  \Phi(\{a_2,\ldots,a_k\},n) + \Phi(\{a_2,\ldots,a_k\},\gcd(a_1,n) ) \\
  &amp;=
  \sum_{d|n}\mu(d) 2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)}
   +
   \sum_{d|(a_1,n)}\mu(d) 2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;=
  2 \sum_{d|(a_1,n)}\mu(d) 2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)}
   +
   \sum_{\substack{d|n\\ d\nmid a_1}}\mu(d) 2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;=
  \sum_{d|(a_1,n)}\mu(d) 2^{\lfloor \frac{a_1}{d} \rfloor - \lfloor \frac{a_1-1}{d} \rfloor}
  2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;\quad +
   \sum_{\substack{d|n\\ d\nmid a_1}}\mu(d) 2^{\sum_{i=1}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;=
  \sum_{d|(a_1,n)}\mu(d) 2^{\sum_{i=1}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)}
   +
   \sum_{\substack{d|n\\ d\nmid a_1}}\mu(d) 2^{\sum_{i=1}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;=
  \sum_{d|n}\mu(d) 2^{\sum_{i=1}^k
   (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)}.
   \end{split}
   \]
  (b) Similar.
   \end{proof}
 \begin{corollary} \label{phi-union}
 Let $l_1,l_2,\ldots,l_k$ and $m_1,m_2,\ldots,m_k$ be nonnegative integers such that
 $l_i &lt; m_i$ for $i=1,2,\ldots,k$ and $m_i \leq l_{i+1}$ for $i=1,2,\ldots,k-1$. Then
 \[ (a)\quad
 \Phi([l_1 +1,m_1]\cup [l_2 +1,m_2]\cup\ldots\cup [l_k +1,m_k], n) =
 \sum_{d|n} \mu(d) 2^{\sum_{i=1}^{k}(\lfloor \frac{m_i}{d} \rfloor - \lfloor\frac{l_i}{d} \rfloor)}.
 \]
 \[ (b)\quad
 \Phi_{\alpha}([l_1 +1,m_1]\cup [l_2 +1,m_2]\cup\ldots\cup [l_k +1,m_k], n) =
 \sum_{d|n} \mu(d)\binom{\sum_{i=1}^{k}(\lfloor \frac{m_i}{d} \rfloor - \lfloor\frac{l_i}{d} \rfloor)}{\alpha}.
 \]
 \end{corollary}
 \begin{proof}
 Apply Theorem \ref{main1} to the set
 \[
 A= \{l_1 +1,l_1 +2,\ldots,m_1, l_2 +1,l_2 +2,\ldots,m_2,\ldots,l_k +1,l_k +2,\ldots,m_k \}.
 \]
 \end{proof}
 \begin{corollary} \label{parity}
 If $n \in A$, then $\Phi(A,n) \equiv 0 \bmod 2$.
 \end{corollary}
 \begin{proof}
 Note first that
 \[
 \sum_{a\in A} \left(\left\lfloor \frac{a}{d} \right\rfloor - \left\lfloor \frac{a-1}{d} \right\rfloor\right)
 \]
 counts the number of multiples of $d$ in the set $A$. So,
 if $n\in A$, then evidently $\sum_{a\in A}(\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor) &gt;0$ for all divisor $d$ of $n$ and thus the required congruence follows by Theorem \ref{main1}(a).
 \end{proof}
 \section{Relatively prime subsets of integer sets} \label{sec:function-f}
 \begin{theorem} \label{main2}
  We have
 \[ (a)\quad
  f(A)= \sum_{d=1}^{\sup A}\mu(d) \left(2^{\sum_{a\in A}(\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor)} -1\right).
 \]
 \[ (b)\quad
  f_{\alpha}(A)= \sum_{d=1}^{\sup A}\mu(d) \binom{\sum_{a\in A}(\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor)}{\alpha}. \]
 \end{theorem}
 \begin{proof}
 (a) We use induction on $|A|$.
 If $A=\{a \}=[a,a]$, then by Theorem \ref{relprime-interval} (a)
  \[ f(A)= \sum_{d=1}^a \mu(d) \left(2^{\lfloor \frac{a}{d} \rfloor - \lfloor \frac{a-1}{d} \rfloor}-1\right). \]
  Assume now that $A= \{a_1,a_2,\ldots,a_k\}$ and that the identity is true for $\{a_2,\ldots,a_k\}$. Without loss of generality
  we may assume that $a_1 &lt; \sup A$. Then, with the help
  of Theorem~\ref{main1}(a), we have
 $$ f(\{a_1,\ldots,a_k\}) = $$
 \begin{eqnarray*}
  \hphantom{a} &amp;=&amp;
  f(\{a_2,\ldots,a_k\}) + \Phi(\{a_2,\ldots,a_k\},a_1) ) \\
  &amp;=&amp;
  \sum_{d=1}^{\sup A}\mu(d) \left(2^{\sum_{i=2}^k
   (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right) 
   + \sum_{d|a_1} \mu(d)2^{\sum_{i=2}^k
   (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;=&amp;
  \sum_{d| a_1}\mu(d)
    \left(2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right) 
   +
    \sum_{\substack {d=1 \\ d \nmid a_1}}^{\sup A}\mu(d)
    \left(2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right) 
  +
   \sum_{d|a_1} \mu(d)2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;=&amp;
  2 \sum_{d|a_1} \mu(d)2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)}
    - \sum_{d|a_1}\mu(d) 
    +
    \sum_{\substack {d=1 \\ d \nmid a_1}}^{\sup A}\mu(d)
    \left(2^{\sum_{i=2}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right) \\
  &amp;=&amp;
  \sum_{d|a_1}\mu(d) \left(
    2^{\sum_{i=1}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right) 
   +
    \sum_{\substack {d=1 \\ d \nmid a_1}}^{\sup A}\mu(d)
    \left(2^{\sum_{i=1}^k (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right) \\
  &amp;=&amp;
    \sum_{d=1}^{\sup A}\mu(d) \left(2^{\sum_{i=1}^k
   (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} -1\right).
  \end{eqnarray*}

  (b) Similar.
 \end{proof}

 \begin{corollary} \label{f-union}
 Let $l_1,l_2,\ldots,l_k$ and $m_1,m_2,\ldots,m_k$ be nonnegative integers such that
 $l_i &lt; m_i$ for $i=1,2,\ldots,k$ and $m_i \leq l_{i+1}$ for $i=1,2,\ldots,k-1$. Then
 \[ (a)\quad
 f([l_1 +1,m_1]\cup [l_2 +1,m_2]\cup\ldots\cup [l_k +1,m_k]) =
 \sum_{d=1}^{\sup A} \mu(d) \left(2^{\sum_{i=1}^{k}(\lfloor \frac{m_i}{d} \rfloor - \lfloor\frac{l_i}{d} \rfloor)}-1\right).
 \]
 \[ (b)\quad
 f_{\alpha}([l_1 +1,m_1]\cup [l_2 +1,m_2]\cup\ldots\cup [l_k +1,m_k], n) =
 \sum_{d=1}^{\sup A} \mu(d)\binom{\sum_{i=1}^{k}(\lfloor \frac{m_i}{d}\rfloor - \lfloor\frac{l_i}{d} \rfloor)}{\alpha}.
 \]
 \end{corollary}
 \begin{proof}
 Apply Theorem \ref{main2} to the set
 \[
 A= \{l_1 +1,l_1 +2,\ldots,m_1, l_2 +1,l_2 +2,\ldots,m_2,\ldots,l_k +1,l_k +2,\ldots,m_k \}.
 \]
 \end{proof}
 \noindent
 Alternatively, we have the following formulas for $f(A)$ and $f_{\alpha}(A)$.
 \begin{theorem} \label{main3}
 Let $A= \{a_1,a_2,\ldots,a_k\}$, let $\tau$ be a permutation of $\{1,2,\ldots,k\}$, and let
 $A_{\tau(j)} =\{a_{\tau(1)},a_{\tau(2)},\ldots, a_{\tau(j)} \}$ for $j=1,2,\ldots,k$. Then
 \[ (a)\quad
  f(A)= \sum_{d\mid a_{\tau(1)}} \mu(d) + \sum_{j=2}^k \sum_{ d|a_{\tau(j)} } \mu(d)
  2^{\sum_{i=1}^{j-1}
   (\lfloor \frac{a_{\tau(i)}}{d}\rfloor - \lfloor \frac{a_{\tau(i)} -1}{d}\rfloor)}.
 \]
 \[ (b) \quad
 f_{\alpha}(A) = \sum_{j=1}^k \sum_{ d|a_{\tau(j)} } \mu(d) \binom{\sum_{i=1}^{j-1}
   (\lfloor \frac{a_{\tau(i)}}{d}\rfloor - \lfloor \frac{a_{\tau(i)} -1}{d}\rfloor)}{\alpha -1}.
 \]
 \end{theorem}
 \begin{proof}
 For simplicity we assume that $\tau$ is the identity permutation.
 As to part (a) we have with the help of Theorem~\ref{main1}
 \[
  \begin{split}
  f(\{a_1,\ldots,a_k\})
  &amp;=
  f(\{a_1,\ldots,a_{k-1}\}) + \Phi(\{a_1,\ldots,a_{k-1}\},a_k)  \\
  &amp;=
  f(\{a_1\}) + \Phi(\{a_1\},a_2) + \ldots + \Phi(\{a_1,\ldots,a_{k-1}\},a_k)  \\
  &amp;=
  \sum_{d|a_1} \mu(d) + \sum_{d|a_2}\mu(d)
   2^{\left \lfloor \frac{a_1}{d} \rfloor - \lfloor \frac{a_1 -1}{d} \right\rfloor}\\
   &amp;\quad + \ldots +
   \sum_{d|a_k} \mu(d) 2^{\sum_{i=1}^{k-1}
   (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)} \\
  &amp;= \sum_{d|a_1} \mu(d) +
   \sum_{j=2}^k \sum_{d|a_j} \mu(d) 2^{\sum_{i=1}^{j-1}
   (\lfloor \frac{a_i}{d}\rfloor - \lfloor \frac{a_i -1}{d}\rfloor)},
  \end{split}
  \]
  where the third formula follows from Theorem \ref{main1}.
  Part (b) follows similarly.
 \end{proof}
 \section{Combinatorial identities and Diophantine equations}
\noindent
 We now give some identities involving Mertens function which provide solutions to a type of Diophantine equations.
 \begin{theorem} \label{Mertens-m,n}
 Let $m$ and $n$ be positive integers such that $1 &lt; m &lt; n$. Then
 \[  \sum_{d=1}^n \mu(d)
  2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} =
  \begin{cases}
 M(n),\ \text{if $\gcd(m,n) &gt;1$;} \\
 1 + M(n),\ \text{if $\gcd(m,n)=1$.}
 \end{cases}
 \]
 \end{theorem}
 \begin{proof}
 If $\gcd(m,n) &gt;1$, then clearly have $f(\{m, n\}) = 0$. If $1&lt;m\leq n$ and $\gcd(m,n)=1$, then clearly
 $f(\{m,n\}) = 1$.
 On the other hand, by Theorem~\ref{main2} (a) applied to the set $\{m,n \}$ we have
 \[
 \begin{split}
 f(\{m,n\}) &amp;= \sum_{d=1}^n  \mu(d)
  \big( 2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} - 1 \big) \\
 &amp; = \sum_{d=1}^n  \mu(d)
  2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} - M(n).
 \end{split}
 \]
 Combining the identities for $f(\{m,n\})$ for the case $\gcd(m,n) &gt;1$ gives
 \[
  M(n) = \sum_{d=1}^n \mu(d)
  2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor}
  \]
  and for the case $1&lt;m\leq n$ and $\gcd(m,n)=1$ gives
  \[
  1+ M(n) = \sum_{d=1}^n \mu(d)
  2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor}.
  \]
 This completes the proof.
 \end{proof}
 \noindent
 In terms of Diophantine equations Theorem~\ref{Mertens-m,n} translates into the following.
 \begin{corollary} \label{corol1}
 Let $1&lt;m &lt;n$ be positive integers. Then
 \noindent
 (a)\ If $\gcd(m,n) =1$, then $(2,1)$ is a solution to the equation
  \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 1.
 \]
 \noindent
 (b)\ If $\gcd(m,n) &gt; 1$, then $(1,2)$ and $(2,1)$ are solutions to the equation
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 0.
 \]
 \end{corollary}
 \begin{proof}
 Immediate from Theorem~\ref{Mertens-m,n}.
 \end{proof}
 \begin{theorem} \label{Mertens-l,m,n}
 Let $l$, $m$, and $n$ be integers such that $1 &lt; l&lt; m &lt; n$. Then
 \[  \sum_{d=1}^n \mu(d)
  2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor +
   \lfloor\frac{l}{d} \rfloor - \lfloor \frac{l-1}{d} \rfloor} = \]
 \[
  \begin{cases}
 4+ M(n),\ \text{if $\gcd(l,m)=\gcd(l,n)=\gcd(m,n) =1$;} \\
 3+ M(n),\ \text{if exactly two pairs from $\{l,m,n\}$ are co-prime;}\\
 2+ M(n),\ \text{if exactly one pair from $\{l,m,n\}$ is co-prime;}\\
 1 + M(n),\ \text{if no pair from $\{l,m,n\}$ is co-prime and $\gcd(l,m,n)=1$;} \\
 M(n),\ \text{otherwise.}
 \end{cases}
 \]
 \end{theorem}
 \begin{proof}
 Suppose that $1&lt;l&lt;m&lt;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\},\ \text{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~\ref{main2} (a) we get
 \[
 \sum_{d=1}^n \mu(d)
  (2^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor +
   \lfloor\frac{l}{d} \rfloor - \lfloor \frac{l-1}{d} \rfloor} - 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 ~\ref{main2} (a).
 The remaining three cases follow similarly and the proof is completed.
 \end{proof}
 \noindent
 In terms of Diophantine equations Theorem~\ref{Mertens-l,m,n} means the following.
 \begin{corollary} \label{corol2}
 Let $l,m,n$ be integers such that $1&lt;l&lt;m&lt;n$. Then

 \noindent
 (a) If $\gcd(l,m)=\gcd(l,n)=\gcd(m,n)=1$, then $(2,1)$ is a solution to
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 4.
  \]
  (b) If exactly two pairs from $\{l,m,n\}$ are co-prime, then $(2,1)$ is a solution to
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 3.
  \]
 (c) If exactly one pair from $\{l,m,n\}$ is co-prime, then $(2,1)$ is a solution to
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 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
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 1.
  \]
 (e) Otherwise, the integer pairs $(1,2)$ and $(2,1)$ are solutions to
 \[
 \sum_{d=1}^n \mu(d)
  \big( x^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} -
  y^{\lfloor\frac{n}{d} \rfloor - \lfloor \frac{n-1}{d} \rfloor + \lfloor\frac{m}{d} \rfloor - \lfloor \frac{m-1}{d} \rfloor} \big)
  = 0.
  \]
 \end{corollary}
 \begin{proof}
 Straightforward from Theorem~\ref{Mertens-l,m,n}.
 \end{proof}
 \noindent
 We close the paper by some open questions which are suggested by our results.
 \\ \\
 \noindent
 {\bf Open Questions.} \\ \\
 \noindent
 {\bf Question 1.} Do the Diophantine equations in Corollary~\ref{corol1} and Corollary~\ref{corol2} have any other real solutions?

 \noindent
 {\bf Question 2.} Do the Diophantine equations in Corollary~\ref{corol1} and Corollary~\ref{corol2} have any other integer solutions?

 \noindent
 {\bf Question 3.} It is clear that any real pair $(x,x)$ is a solution to the equation in part (b) of Corollary~\ref{corol1} and
 to the equation in part (e) of  Corollary~\ref{corol2}. These solutions might be called \emph{trivial}.
 Is the number of \emph{non-trivial} integer solutions to the equations in Corollary~\ref{corol1} and Corollary~\ref{corol2}
 finite?

\section{Acknowledgments}
The author is grateful to the referee
 for valuable comments and interesting suggestions.

 \begin{thebibliography}{9}

 \bibitem{Ayad-Kihel1}
 M. Ayad and O. Kihel,
 On the number of subsets relatively prime to an integer,
 {\it J. Integer Sequences} {\bf 11}, (2008), 
 \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Ayad/ayad3.html}{Article 08.5.5}.

 \bibitem{Ayad-Kihel2}
 M. Ayad and O. Kihel,
 On relatively prime sets,
 {\it Integers} {\bf 9} (2009), 343--352.  Available
 electronically at \url{http://www.integers-ejcnt.org/vol9.html}.

 \bibitem{ElBachraoui1}
 M. El Bachraoui,
 The number of relatively prime subsets and phi functions for sets $\{m,m+1,\ldots,n\}$,
 {\it Integers} {\bf 7} (1)
 (2007), A43.  Available electronically at
 \url{http://www.integers-ejcnt.org/vol7.html}.

 \bibitem{ElBachraoui2}
 M. El Bachraoui,
 On the number of subsets of $[1,m]$ relatively prime to $n$ and asymptotic estimates,
 {\it Integers} {\bf 8} (1) (2008), A41.  Available
 electronically at \url{http://www.integers-ejcnt.org/vol8.html}.

 \bibitem{Nathanson}
  M. B. Nathanson,
  Affine invariants, relatively prime sets, and a phi function for subsets of $\{1,2,\ldots,n\}$,
  {\it Integers} {\bf 7} (1)
  (2007), A1.
  Available electronically at
  \url{http://www.integers-ejcnt.org/vol7.html}.

 \bibitem{Nathanson-Orosz}
  M. B. Nathanson and B. Orosz,
  Asymptotic estimates for phi functions for subsets of $\{m+1, m+2,\ldots,n\}$,
  {\it Integers} {\bf 7} (2007), A54.
  Available electronically at
  \url{http://www.integers-ejcnt.org/vol7.html}.

 \bibitem{Tang}
 M. Tang,
 Relatively prime sets and a phi function for subsets of $\{1,2,\ldots,n\}$,
 {\it J. Integer Sequences} {\bf 13} (2010), 
 \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Tang/tang2.html}{Article 10.7.6}.

 \bibitem{Toth}
 L. T\'oth,
 On the number of certain relatively prime subsets of $\{1,2,\ldots,n\}$,
 {\it Integers} {\bf 10} (2010), A35, 407--421.
 Available electronically at \url{http://www.integers-ejcnt.org/vol10.html}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A25; Secondary 11B05, 11B75, 11D41.

\noindent \emph{Keywords: } 
phi function, relatively prime set, Mertens function, M\"obius function, 
combinatorial identities, Diophantine equation.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 23 2011;
revised version received  February 2 2012; March 14 2012.
Published in {\it Journal of Integer Sequences}, March 25 2012.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>