\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) &= \# \{X\subseteq A:\ X\not= \emptyset\ \text{and\ } \gcd(X) = 1 \}, \\ f_{\alpha} (A) &= \# \{X\subseteq A:\ \# X= \alpha \ \text{and\ } \gcd(X) = 1 \}, \\ \Phi(A,n) &= \# \{X\subseteq A:\ X\not= \emptyset\ \text{and\ } \gcd(X,n) = 1 \}, \\ \Phi_{\alpha} (A,n) &= \# \{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]) &= \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]) &= \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) &= \sum_{d|n} \mu(d)2^{\lfloor\frac{m}{d}\rfloor - \lfloor\frac{l-1}{d}\rfloor}, \\ (d)\quad \phi_{\alpha}([l,m],n) &= \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) &= \Phi(\{a_2,\ldots,a_k\},n) + \Phi(\{a_2,\ldots,a_k\},\gcd(a_1,n) ) \\ &= \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)} \\ &= 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)} \\ &= \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)} \\ &\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)} \\ &= \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)} \\ &= \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 < 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) >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 < \sup A$. Then, with the help of Theorem~\ref{main1}(a), we have $$ f(\{a_1,\ldots,a_k\}) = $$ \begin{eqnarray*} \hphantom{a} &=& f(\{a_2,\ldots,a_k\}) + \Phi(\{a_2,\ldots,a_k\},a_1) ) \\ &=& \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)} \\ &=& \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)} \\ &=& 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) \\ &=& \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) \\ &=& \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 < 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\}) &= f(\{a_1,\ldots,a_{k-1}\}) + \Phi(\{a_1,\ldots,a_{k-1}\},a_k) \\ &= f(\{a_1\}) + \Phi(\{a_1\},a_2) + \ldots + \Phi(\{a_1,\ldots,a_{k-1}\},a_k) \\ &= \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}\\ &\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)} \\ &= \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 < m < 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) >1$;} \\ 1 + M(n),\ \text{if $\gcd(m,n)=1$.} \end{cases} \] \end{theorem} \begin{proof} If $\gcd(m,n) >1$, then clearly have $f(\{m, n\}) = 0$. If $11$ 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 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 < l< m < 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