\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf On the Number of Subsets Relatively Prime \\
\vskip .12in
to an Integer
}
\vskip 1cm
\large
Mohamed Ayad \\
Laboratoire de Math{\'e}matiques Pures et Appliqu{\'e}es\\
Universit\'e du Littoral\\
F-62228 Calais\\
France \\
\href{ayad@lmpa.univ-littoral.fr}{\tt ayad@lmpa.univ-littoral.fr} 
\ \\
Omar Kihel \\
Department of Mathematics\\
Brock University \\
St. Catharines, Ontario L2S 3A1\\
Canada \\
\href{okihel@brocku.ca}{\tt okihel@brocku.ca} \\
\end{center}

\vskip .2 in

\begin{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.
\end{abstract} 

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Example}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}


\section{Introduction}

A nonempty subset $A$ of $\{1,\, 2,\, \ldots,\,  n \}$ is
said to be relatively prime if $\gcd(A)=1$.  Nathanson \cite{Nathanson 1}
defined $f(n)$ to be the number of relatively prime subsets of
$\{1,\, 2,\, \ldots,\,  n \}$ and, for $k\geq 1$, $f_{k}(n)$ to be
the number of relatively prime subsets of $\{1,\, 2,\, \ldots,\, n
\}$ of cardinality $k$. Nathanson \cite{Nathanson 1} defined $\Phi (n)$ to
be the number of nonempty subsets $A$ of the set $\{1,\, 2,\,
\ldots,\,  n \}$ such that gcd$(A)$ is relatively prime to $n$
and, for integer $k\geq 1$, ${\Phi}_{k}(n)$ to be the number of
subsets $A$ of the set $\{1,\, 2,\, \ldots,\,  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 \cite{El Bachraoui 2} to subsets  $A \in \{m+1,\, m+2,\, \ldots, n
\}$ where $m$ is any nonnegative integer, and then by Ayad and
Kihel \cite{Ayad} to subsets of the set $\{a,\, a + b,\, \ldots, \,
a+ (n-1)b
\}$ where $a$ and $b$ are any integers. \\
\par El Bachraoui \cite{El Bachraoui 1} defined for any given positive integers $l\leq m \leq n$,
$\Phi ([l,m],n)$ to be the number of nonempty subsets of
$\{l,\,l+1,\, \ldots,\,  m \}$ which are relatively prime to $n$
and $\Phi_{k} ([l,m],n)$ to be the number of such subsets of
cardinality $k$. He
found formulas for these functions
when $l = 1$ \cite{El Bachraoui 1}.
In this paper, we generalize these functions and
obtain El Bachraoui's result as a particular case.


\section{Phi functions for
 $\{1,\, 2,\, \ldots,\,  m\}$} Let $k$ and $l \leq m \leq n$ be positive integers. 
 Let $\lfloor x\rfloor$ denote the greatest integer less
than or equal to $x$, and $\mu(n)$ the M$\ddot{o}$bius function.
El Bachraoui \cite{El Bachraoui 1} defined $\Phi ([l,m],n)$ to be the number of
nonempty subsets of $\{l,\,l+1,\, \ldots,\,  m \}$ which are
relatively prime to $n$ and $\Phi_{k} ([l,m],n)$ to be the number
of such subsets of cardinality $k$. He 
proved the
following formulas
\cite{El Bachraoui 1}:

\begin{equation}
\Phi([1,m],n) = \sum_{d \mid n} \mu(d) 2^{[\frac{m}{d}]}
\label{2.1}
\end{equation}
and
\begin{equation}
\Phi_{k}([1,m],n) = \sum_{d \mid n} \mu(d) \left( \begin{array}{c}
[\frac{m}{d}]
\\ k \end{array} \right).
\label{2.2}
\end{equation}


In his proof of Eqs.~(\ref{2.1}) and (\ref{2.2}),
El Bachraoui \cite{El Bachraoui 1}
used the M$\ddot{o}$bius inversion formula and its extension
to functions of several variables. The case $m=n$ in (\ref{2.1}),
was proved by Nathanson \cite{Nathanson 1}.

\section{Phi functions for  $\{ a,\, a + b,\,  \ldots,\,  a + (m-1)b \}$}

It is natural to ask whether one can generalize the formulas
obtained by El Bachraoui \cite{El Bachraoui 1} to a set $A = \{ a,\, a + b,\,
\ldots,\, a + (m-1)b \}$, where $a$, $b$, and $m$ are positive
integers. Let $\Phi^{(a,b)} (m,n)$ be the number of nonempty
subsets of $\{ a,\, a + b,\,  \ldots,\,  a + (m-1)b \}$ which are
relatively prime to $n$ and $\Phi_{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 \cite{Ayad}:

\begin{lemma}\label{Lemma}
For an integer $d \geq 1$, and for nonzero integers $a$ and $b$
such that $\gcd(a, b)=1$, let $A_{d}= \{ x = a + ib \;
{\mbox{for}}\; i = 0, \ldots
,(m-1) \Bigl| \; d \mid x \}$. Then \\
(i) If gcd $(b,d) \neq 1$, then $ |A_{d}| =0$.\\
(ii) If gcd $(b,d) = 1$, then $|A_{d}| = \lfloor \frac{m}{d} \rfloor
+ \varepsilon_{d}$, where
\begin{equation}
\varepsilon_{d} = \left\{ \begin{array}{ll} 0, & \mbox{if } \;  d \; \mid \; m ;\\
1, & \mbox{if } d \; \nmid \; m \mbox{ and } (-ab^{-1})\bmod d \in \left\{ 0, \ldots, m- \lfloor \frac{m}{d} \rfloor d - 1 \right\}; \\
0, & \mbox{otherwise.} \end{array} \right.
\end{equation}
\end{lemma}

\begin{theorem}\label{Theorem}
\begin{equation}
\Phi^{(a, b)}(m,n) = \sum_{\begin{array}{c} d | n \\
\gcd(b,d)=1 \end{array}} \mu(d) \left( 2^{ \lfloor\frac{m}{d}\rfloor
+\epsilon_{d}} - 1 \right)
\end{equation}
and
\begin{equation}
\Phi_{k}^{(a,b)}(m,n) = \sum_{\begin{array}{c} d | n \\
\gcd(b,d)=1 \end{array}} \mu(d) \left( \begin{array}{c}
\lfloor\frac{m}{d}\rfloor +\epsilon_{d}
\\ k \end{array} \right),
\label{3.3}
\end{equation}
where $\epsilon_{d}$ is the function defined in Lemma \ref{Lemma}.
\end{theorem}

\begin{proof} Let $A_{d}= \{ x = a + ib \; {\mbox{for}}\; i
= 0, \ldots ,(m-1) \Bigl| \; d \mid x \}$, and
 $\mathcal{P}(A_{d}) = \{ \mbox{the
nonempty subsets of}\,  A_{d}\}.$ It is easy to see that
$\Phi^{(a, b)}(m,n) = (2^{m}-1) - \biggl|
\displaystyle{\bigcup_{\displaystyle{\begin{array}{c} p \mbox{
prime} \\ p \mid n \end{array}}}} \mathcal{P} (A_{p}) \biggr|.$
Clearly, if $p_{1}, \ldots, p_{t}$ are distinct primes, then
\[
\left| \bigcap_{i=1}^{t} \mathcal{P}(A_{p_{i}}) \right| =
\left|\mathcal{P}(A_{\prod_{i=1}^{t}p_{i}}) \right|.
\] Thus, using the principle of inclusion-exclusion, one obtains
from above that
$$\Phi^{(a, b)}(m,n) = \sum_{\begin{array}{c} d | n \end{array}} \mu(d) |\mathcal{P} (A_{d})|.$$ \noindent
It was proved in Lemma \ref{Lemma}, that if $\gcd(b,d) \neq 1 $, then
$|A_{d}|= 0$ and if $\gcd(b,d) = 1 $, then
$|A_{d}|=\displaystyle{{\left(\lfloor \frac{m}{d} \rfloor +
\varepsilon_{d}\right)} }$. Hence
$$\Phi^{(a, b)}(m,n) = \sum_{\begin{array}{c} d | n \\
\gcd(b,d)=1 \end{array}} \mu(d) \left( 2^{[\frac{m}{d}] +
\epsilon_{d}} - 1 \right).$$ The proof for Eq.~(\ref{3.3}) is similar.
\end{proof}

\noindent Theorem 3 in \cite{El Bachraoui 1} can be deduced from
Theorem~\ref{Theorem} above as the particular case where $a\,=\, b \,
=\, 1$. We prove the following.

\begin{corollary}\label{Corollary}
(a) $\Phi([1,m],n) = \Phi^{(1, 1)}(m,n)$ \\
and \\
(b) $\Phi_{k}([l,m],n) = \Phi_{k}^{(1, 1)}(m,n)$ .
\end{corollary}

\begin{proof} 
It is not difficult to prove that when $a \, =
\,  b\, =\, 1$ in Lemma~\ref{Lemma}, $\epsilon_{d} = 0$.
Using Theorem~\ref{Theorem},
and the well-known equality $\sum_{d\mid n}\mu(d)=0$, one
obtains that
\begin{equation}
\Phi^{(1, 1)}(m,n) = \sum_{ d | n }
\mu(d) \left( 2^{ \lfloor \frac{m}{d}\rfloor } - 1
\right) = \sum_{\begin{array}{c} d | n \\
\end{array}} \mu(d)  2^{ \lfloor\frac{m}{d}\rfloor }
 = \Phi([1,m],n)
\end{equation}
and
\begin{equation}
\Phi_{k}^{(1,1)}(n) = \sum_{ d | n } \mu(d) \left( \begin{array}{c}
\lfloor\frac{m}{d}\rfloor
\\ k \end{array} \right) = \Phi_k([1,m],n).
\end{equation}
\end{proof}

\begin{remark}
Using Theorem \ref{Theorem}, one can obtain asymptotic estimates and
generalize Corollary 4 proved by  El Bachraoui \cite{El Bachraoui 1}.
\end{remark}



\begin{thebibliography}{99}
\bibitem{Ayad} M. Ayad and O. Kihel, On relatively prime sets,
submitted.

\bibitem{El Bachraoui 1} M. El Bachraoui, On the number of subsets of $[1,m]$
relatively prime to $n$ and asymptotic estimates,
\textit{Integers} \textbf{8} (2008), A41, 5 pp. (electronic).

\bibitem{El Bachraoui 2}  M. El Bachraoui, The number of relatively prime
subsets and phi functions for $\{m, m+1, \ldots, n \}$, \textit{Integers}
\textbf{7} (2007), A43, 8 pp. (electronic).

\bibitem{Nathanson 1} M. B. Nathanson, Affine invariants, relatively prime
sets, and a phi function for subsets of $\{1,\, 2,\, \ldots,\,  n
\}$, \textit{Integers} \textbf{7} (2007), A1, 7 pp. (electronic).

\bibitem{Nathanson 2} M. B. Nathanson and B. Orosz, Asymptotic estimates for
phi functions for subsets of $\{M+1, M+2,\ldots, N \}$, \textit{Integers}
\textbf{7} (2007), A54, 5 pp. (electronic).

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15.

\noindent \emph{Keywords: } relatively prime subset,
Euler phi function.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 22 2008;
revised version received December 13 2008. 
Published in {\it Journal of Integer Sequences},
December 13 2008.

\bigskip
\hrule
\bigskip

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


\end{document}