\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
Relatively Prime Sets and a Phi Function   \\
\vskip .1in for Subsets of $\{1,2,\ldots,n\}$ } \vskip 1cm \large
Min Tang\footnote{Supported by the National Natural Science
Foundation of China, Grant No.\
10901002.}\\
Department of Mathematics \\
Anhui Normal University\\
Wuhu 241000 \\
P. R. China\\
\href{mailto:tmzzz2000@163.com}{\tt tmzzz2000@163.com} \\
\end{center}

\vskip .2in


\begin{abstract}
A nonempty subset $A$ of $\{1,2,\ldots,n\}$ is said to be relatively
prime if $\gcd(A)=1$. Let $f(n)$ and $f_k(n)$ denote 
the number of relatively prime subsets and the number of relatively
prime subsets of cardinality $k$ of $\{1,2,\ldots,n\}$, respectively. Let
$\Phi(n)$ and $\Phi_k(n)$ denote the number of nonempty
subsets and the number of subsets of cardinality $k$ of
$\{1,2,\ldots,n\}$ such that $\gcd(A)$ is relatively prime to $n$,
respectively.
In this paper, we obtain some properties of these functions.
\end{abstract}

\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}

\section{Introduction}

A nonempty subset $A$ of $\{1,2,\ldots,n\}$ is said to be {\it relatively
prime\/} if $\gcd(A)=1$. Nathanson \cite{Nathan} defined $f(n)$ to be
the number of relatively prime subsets of $\{1,2,\ldots,n\}$, and
for $k\geq 1$, he defined $f_k(n)$ to be the number of relatively prime subsets
of cardinality $k$ of $\{1,2,\ldots,n\}$.  
Nathanson \cite{Nathan}
defined $\Phi(n)$ and $\Phi_k(n)$, respectively, to be the number of
nonempty subsets and the number of subsets of cardinality $k$ of
$\{1,2,\ldots,n\}$ such that $\gcd(A)$ is relatively prime to $n$.
Sloane's sequence
\seqnum{A085945} enumerates $f(n)$ and
\seqnum{A027375} enumerates $\Phi(n)$.
Let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$,
$\varphi(n)$ the Euler phi function and $\mu(n)$ the M\"obius
function. Nathanson \cite{Nathan} obtained the following explicit
formulas for these functions.

\bigbreak

\begin{theorem}\label{thm1} The following hold:

$(a)$ For all positive integers $n$,
\begin{equation} \label{eq:asymP}
f(n)=\sum_{d=1}^n\mu(d)\big(2^{ \lfloor n/d \rfloor }-1\big).
\end{equation}

$(b)$ For all positive integers $n\geq 2$,
\begin{equation} \label{eq:asym2}\Phi(n)=\sum_{d\mid n}\mu(d)2^{n/d}.
\end{equation}

$(c)$ For all integers $n$ and $k$,
\begin{equation} \label{eq:asym3}
f_{k}(n)=\sum_{d=1}^n \mu(d)\binom{ \lfloor n/d \rfloor }{k}.
\end{equation}

$(d)$ For all integers $n$ and $k$,
\begin{equation} \label{eq:asym4}\Phi_{k}(n)=\sum_{d\mid n}\mu(d)\binom{n/d}{k}.
\end{equation}
\end{theorem}

 Generalizations may be found in
 \cite{Ayad2008, Ayad2009, Bach}.
 In 2009, Ayad and Kihel \cite{Ayad} studied some properties of the functions $f(n)$ and $\Phi(n)$. They showed that $f(n)$ is never a square if $n\geq
 2$, and for any prime $l\neq 3$, $f(n)$ is not periodic modulo
 $l$. Moreover, they proved the following equality.
 \begin{theorem}\label{thm2} For any integer $n\geq 1$, we have
\begin{equation} \label{eq:asym5}
f(n+1)-f(n)=\frac{1}{2}\Phi(n+1).
\end{equation}
 \end{theorem}

In this paper, we give a new simple proof of the above result and
obtain some properties of these functions.

\begin{theorem}\label{thm3} For all integers $n$ and $k$, we have
\begin{equation} \label{eq:asym6}
\Phi_{k}(n+1)=f_{k}(n+1)-f_k(n)+f_{k+1}(n+1)-f_{k+1}(n).
\end{equation}
\end{theorem}

\begin{remark}
Note that for any positive integers $n$, $f_1(n+1)=f_1(n)=1$. By Theorem
\ref{thm3}, we have $f_{2}(n+1)-f_2(n)=\Phi_{1}(n+1)=\varphi(n+1)$.
Thus for $n\geq 2$, we have $f_2(n+1)-f_2(n)\equiv 0\pmod 2,$ and
$f_2(2)=1$, thus $f_2(n)\equiv 1\pmod 2$ for all $n\geq 2$.
\end{remark}

\begin{remark}
By Theorem \ref{thm3}, for all $n\geq 2$ we have
$f_2(n)-f_2(n-1)=\varphi(n)$. Thus $$\sum_{2\leq i\leq
n}\varphi(i)=\sum_{2\leq i\leq n}\Big(f_2(i)-f_2(i-1)\Big)=f_2(n),$$
hence $$f_2(n)=\frac{3n^2}{\pi^2}+O(n\log n).$$
\end{remark}

\begin{remark}
Let $p,q$ be primes. Note that $\Phi(p)=2^p-2$ and
$\Phi(pq)=2^{pq}-2^p-2^q+2$. Thus $\Phi(p)\equiv \Phi(pq)\equiv 2\pmod
4$. And $\Phi(n)\equiv 0\pmod 3$ for all $n\geq 3$ (see
\cite{Ayad}); thus $\Phi(p)\equiv \Phi(pq)\equiv 6\pmod {12}$. Hence
$\Phi(p)$ and $\Phi(pq)$ are neither a square nor a cube.
\end{remark}
\vskip .2 in

 To prove Theorem \ref{thm2} and \ref{thm3}, we need the
following lemma.
\begin{lemma}\label{lem1}  For all integers $n$ and $k$,
$$\Big\lfloor \frac{n+1}{k}\Big \rfloor -\Big\lfloor \frac{n}{k}\Big \rfloor =\left\{
\begin{array}{l}
1,\quad \textnormal{ if }k\mid (n+1);  \\
0,\quad \textnormal{ otherwise. }\end{array}\right.$$
 \end{lemma}\vskip 5mm

\section{Proof of Theorem \ref{thm2}.}  By (\ref{eq:asymP}) we have
 $$\begin{array}{ll}f(n+1)-f(n)&=\displaystyle\sum\limits_{d=1}^{n+1}\mu(d)\big(2^{\lfloor \frac{n+1}{d} \rfloor}-1\big)-\sum\limits_{d=1}^n\mu(d)\big(2^{\lfloor n/d \rfloor }-1\big)\\
 &=\displaystyle\sum\limits_{d=1}^n\mu(d)\big(2^{ \lfloor \frac{n+1}{d} \rfloor }-2^{ \lfloor n/d \rfloor }\big)+\mu(n+1).\end{array}$$
 By (\ref{eq:asym2}) and Lemma \ref{lem1}, $$\begin{array}{ll}f(n+1)-f(n)&=\displaystyle\sum\limits_{\substack{ d=1\\d\mid n+1 }
 }^n\mu(d)2^{ \lfloor \frac{n}{d} \rfloor }+\mu(n+1)\\
 &=\displaystyle\sum\limits_{d\mid n+1}\mu(d)2^{ \lfloor n/d \rfloor }\\
 &=\displaystyle\frac{1}{2}\sum\limits_{d\mid n+1}\mu(d)2^{\frac{n+1}{d}}=\frac{1}{2}\Phi(n+1).
 \end{array}$$

\noindent This completes the proof of Theorem \ref{thm2}.\vskip 5mm

\section{Proof of Theorem \ref{thm3}.}
Case 1: $k=1$.
$f_1(n+1)=f_1(n)=1$.
 By (\ref{eq:asym3}) we have$$\begin{array}{ll}f_2(n+1)-f_2(n)&=\displaystyle\sum\limits_{d=1}^{n+1}\mu(d)\binom{ \lfloor \frac{n+1}{d} \rfloor }{2}-\sum\limits_{d=1}^n\mu(d)\binom{\lfloor n/d \rfloor }{2}\\
 &=\displaystyle\sum\limits_{d=1}^n\mu(d)\Bigg(\binom{ \lfloor \frac{n+1}{d} \rfloor }{2}-\binom{ \lfloor n/d \rfloor }{2}\Bigg). \end{array}$$
 By (\ref{eq:asym2}) and Lemma \ref{lem1}, we have $$\begin{array}{ll}f_2(n+1)-f_2(n)&=\displaystyle\sum\limits_{\substack{ d=1\\d\mid n+1 }
 }^n\mu(d)\binom{\frac{n+1}{d}-1}{1}\\
 &=\displaystyle\sum\limits_{\substack{ d=1\\d\mid n+1 }
 }^n\mu(d)\Big(\frac{n+1}{d}-1\Big)\\
 &=\displaystyle\sum\limits_{d\mid n+1}\mu(d)\Big(\frac{n+1}{d}-1\Big)\\
 &=\displaystyle\sum\limits_{d\mid n+1}\mu(d)\frac{n+1}{d}
 =\Phi_1(n+1).
 \end{array}$$

Case 2: $k\geq 2$. By (\ref{eq:asym3}) and Lemma \ref{lem1}, we have$$\begin{array}{ll}f_k(n+1)-f_k(n)&=\displaystyle\sum\limits_{d=1}^{n+1}\mu(d)\binom{ \lfloor \frac{n+1}{d} \rfloor }{k}-\sum\limits_{d=1}^n\mu(d)\binom{ \lfloor n/d \rfloor }{k}\\
 &=\displaystyle\sum\limits_{d=1}^n\mu(d)\Bigg(\binom{ \lfloor \frac{n+1}{d} \rfloor }{k}-\binom{ \lfloor n/d \rfloor }{k}\Bigg)\\
 &=\displaystyle\sum\limits_{d\mid n+1 }
 \mu(d)\binom{ \lfloor \frac{n}{d} \rfloor }{k-1}.\\
  \end{array}$$
  Thus by (\ref{eq:asym4}) and Lemma \ref{lem1}, we have
$$\begin{array}{ll}f_k(n+1)-f_k(n)+f_{k+1}(n+1)-f_{k+1}(n)&=\displaystyle\sum\limits_{d\mid n+1 }\mu(d)\Bigg(\binom{ \lfloor \frac{n}{d} \rfloor }{k-1}+
\binom{ \lfloor \frac{n}{d} \rfloor }{k}\Bigg)\\
 &=\displaystyle\sum\limits_{d\mid n+1 }\mu(d)\binom{ \lfloor \frac{n}{d} \rfloor +1}{k}\\
&=\displaystyle\sum\limits_{d\mid n+1
}\mu(d)\binom{\frac{n+1}{d}}{k}=\Phi_k(n+1).
  \end{array}$$
This completes the proof of Theorem \ref{thm3}.

\section{Acknowledgements} We would like to thank the referees
for their helpful comments.


\begin{thebibliography}{10}

\bibitem{Ayad} M. Ayad and O. Kihel, The number of relatively prime subsets of $\{1,2,\ldots,n\}$, {\it Integers} {\bf 9} (2009), A14.
Available electronically at \href{http://integers-ejcnt.org/vol9.html}{\tt http://integers-ejcnt.org/vol9.html}.

\bibitem{Ayad2008} 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}{Paper 08.5.5}.

\bibitem{Ayad2009} M. Ayad and O. Kihel, On relatively prime sets, {\it Integers} {\bf 9} (2009), A28.
Available electronically at \href{http://integers-ejcnt.org/vol9.html}{\tt http://integers-ejcnt.org/vol9.html}.

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

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

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary 11A25;
Secondary 11B75.

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

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A027375} and
\seqnum{A085945}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 27 2010;
revised version received  July 9 2010.
Published in {\it Journal of Integer Sequences}, July 16 2010.

\bigskip
\hrule
\bigskip

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


\end{document}