\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 A Gcd-Sum Function Over Regular Integers \\ \vskip .1in Modulo $n$ } \vskip 1cm \large L\'aszl\'o T\'oth \\ Institute of Mathematics and Informatics \\ University of P\'ecs \\ Ifj\'us\'ag u. 6 \\ 7624 P\'ecs \\ Hungary \\ \href{mailto:ltoth@ttk.pte.hu}{\tt ltoth@ttk.pte.hu}\\ \end{center} \vskip .2 in \begin{abstract} We introduce a gcd-sum function involving regular integers (mod $n$) and prove results giving its minimal order, maximal order and average order. \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]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \def\Z{{\Bbb Z}} \def\Reg{\operatorname{Reg}} %\newtheorem{theorem}{Theorem} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{thm}{Theorem} \newtheorem{cor}{Corollary} \newtheorem{lem}{Lemma} \newtheorem{rem}{Remark} \newtheorem{prop}{Proposition} \newcommand{\ds}{\displaystyle} \def\lcm{\operatorname{lcm}} \def\N{{\Bbb N}} %************************* section 1 ******************************************* \section{Introduction} Let $n>1$ be an integer with prime factorization $n=p_1^{\nu_1}\cdots p_r^{\nu_r}$. An integer $k$ is called {\it regular} (mod $n$) if there exists an integer $x$ such that $k^2x\equiv k$ (mod $n$), i.e., the residue class of $k$ is a regular element (in the sense of J. von Neumann) of the ring $\Z_n$ of residue classes (mod $n$). In general, an element $k$ of a ring $R$ is said to be (von Neumann) regular if there is an $x\in R$ such that $k=kxk$. If every $k\in R$ has this property, then $R$ is called a {\it von Neumann regular ring}, cf.\ for example \cite[p.\ 110]{Kap1972}. It can be shown that $k\ge 1$ is regular (mod $n$) if and only if for every $i\in \{1,\ldots,r\}$ either $p_i\nmid k$ or $p_i^{\nu_i}\mid k$. Also, $k\ge 1$ is regular (mod $n$) if and only if $\gcd (k,n)$ is a unitary divisor of $n$. We recall that $d$ is said to be a {\it unitary divisor} of $n$ if $d\mid n$ and $\gcd (d,n/d)=1$, and use the notation $d \mid \mid n$. These and other characterizations of regular integers are given in our paper \cite{Tot2008}. Let $\Reg_n=\{k: 1\le k\le n$ and $k$ is regular (mod $n$)$\}$, and let $\varrho(n)=\# \Reg_n$ denote the number of regular integers $k$ (mod $n$) such that $1\le k\le n$. The function $\varrho(n)$ was investigated in paper \cite{Tot2008}. It is multiplicative and $\varrho(p^{\nu})=\phi(p^{\nu})+1= p^{\nu}-p^{\nu-1}+1$ for every prime power $p^{\nu}$ ($\nu \ge 1$), where $\phi$ is the Euler function. Note that $(\varrho(n): n\in \N)$ is the sequence \seqnum{A055653} in Sloane's On-Line Encyclopedia of Integer Sequences. In this paper we introduce the function \begin{equation} \widetilde{P}(n):=\sum_{k\in \Reg_n} \gcd (k,n). \label{gcd-sum_regular} \end{equation} This is analogous to the gcd-sum function, called also Pillai's arithmetical function, \begin{equation} P(n):=\sum_{k=1}^n \gcd (k,n), \label{gcd-sum} \end{equation} investigated in the recent papers \cite{Bor2007a,Bor2007b,Bro2001,Bro2007,TanZha2008} of this journal. This is sequence \seqnum{A018804} in Sloane's Encyclopedia. Note that the function $P(n)$ was introduced by S. S. Pillai \cite{Pil1933}, showing that \begin{equation*} P(n)=\sum_{d\mid n} d\phi(n/d), \ \ \sum_{d\mid n} P(d)=n\tau(n)=\sum_{d\mid n} \sigma(d)\phi(n/d), \end{equation*} where $\tau(n)$ and $\sigma(n)$ denote, as usual, the number and the sum of divisors of $n$, respectively. Note also, that for any arithmetical function $f$, \begin{equation} P_f(n):=\sum_{k=1}^n f(\gcd (k,n))=\sum_{d\mid n} f(d)\phi(n/d), \label{gcd-sum_f} \end{equation} which is a result of E. Ces\`{a}ro \cite{Ces1885}. See also the book \cite[p.\ 127]{Dic1971}. O. Bordell\`{e}s \cite{Bor2007a} showed that \begin{equation} P=\mu*(E\cdot \tau), \label{gcd-sum_convo} \end{equation} where $*$ denotes the Dirichlet convolution, where $E(n)=n$ and $\mu$ is the M\"obius function. Then, using this representation he proved the following asymptotic formula: for every $\varepsilon >0$, \begin{equation} \sum_{n\le x} P(n)=\frac{x^2}{2\zeta(2)}\left(\log x +2\gamma-\frac1{2}-\frac{\zeta'(2)}{\zeta(2)}\right) + {\cal O}(x^{1+\theta+\varepsilon}), \label{gcd-sum_asymptotic} \end{equation} where $\gamma$ is Euler's constant and $\theta$ is the number appearing in Dirichlet's divisor problem, that is \begin{equation} \sum_{n\le x} \tau(n)=x\log x+(2\gamma-1)x+{\cal O}(x^{\theta+\varepsilon}). \label{Dirichlet_divisor} \end{equation} It is known that $1/4\le \theta \le 131/416 \approx 0.3149$. Formulae \eqref{gcd-sum_convo} and \eqref{gcd-sum_asymptotic} were obtained, even in a more general form, in the paper \cite{ChiSit1985}, where the authors proved also the following result concerning the maximal order of $P(n)$, \begin{equation} \limsup_{n\to \infty} \frac{\log(P(n)/n) \log \log n}{\log n}= \log 2, \label{gcd-sum_maximal} \end{equation} which is well known for the function $\tau(n)$ instead of $P(n)/n$. Asymptotic formulae for generalized gcd-sum functions of type \eqref{gcd-sum_f}, concerning sets of polynomials with integral coefficients and regular convolutions were given in our paper \cite{Tot1998}. We investigate in what follows arithmetical and asymptotical properties of the function $\widetilde{P}(n)$. We show that it is multiplicative and for every $n\ge 1$, \begin{equation} \widetilde{P}(n)=n\prod_{p\mid n} \left(2-\frac1{p} \right). \label{gcd-sum_regular_expl} \end{equation} Further, we show that the result \eqref{gcd-sum_maximal} holds also for the function $\widetilde{P}(n)$, its minimal order is $3n/2$ and prove an asymptotic formula for its summatory function both without assuming the Riemann hypothesis and assuming the Riemann hypothesis (RH), based on a convolution identity analogous to \eqref{gcd-sum_convo}. Our results and proofs involve properties of arithmetical functions defined by unitary divisors and of the unitary convolution. For background material in this topic we refer to the book \cite{McC1986}. As an open question we formulate the following: What is the minimal order of the Pillai function $P(n)$? A common generalization of the functions $P(n)$ and $\widetilde{P}(n)$ is outlined at the end of Section 2. %******************** section 2 ***************************************** \section{Arithmetical properties} Let $f$ be an arbitrary arithmetical function and consider the more general function \begin{equation*} \widetilde{P}_f(n):= \sum_{k\in \Reg_n} f(\gcd (k,n)). \end{equation*} \begin{prop} \label{prop_1} For every $n\ge 1$, \begin{equation} \widetilde{P}_f(n)=\sum_{d\mid \mid n} f(d) \, \phi(n/d). \label{gcd-sum_regular_convo1} \end{equation} \end{prop} \begin{proof} The integer $k\ge 1$ is regular iff $\gcd (k,n)\mid \mid n$, cf.\ the Introduction, and obtain \[ \widetilde{P}_f(n)= \sum_{k=1}^n \sum_{d\mid \mid n} f(d)= \sum_{d\mid \mid n} f(d) \sum_{\substack{1\le j\le n/d\\(j,n/d)=1}} 1= \sum_{d\mid \mid n} f(d) \phi(n/d). \] \end{proof} \begin{cor} If $f$ is multiplicative, then $\widetilde{P}_f$ is also multiplicative and $\widetilde{P}_f(p^\nu)= f(p^{\nu})+p^{\nu}- p^{\nu -1}$ for every prime power $p^{\nu}$ ($\nu \ge 1$). In particular, $\widetilde{P}$ is multiplicative and $\widetilde{P}(p^\nu)= 2p^{\nu}-p^{\nu-1}$ for every prime power $p^{\nu}$ ($\nu \ge 1$). \end{cor} \begin{proof} According to \eqref{gcd-sum_regular_convo1}, $\widetilde{P}_f$ is the unitary convolution of the functions $f$ and $\phi$. It is known that the unitary convolution preserves the multiplicativity of functions. In particular, for $f(n)=n$ we obtain that $\widetilde{P}$ is multiplicative and the explicit formula \eqref{gcd-sum_regular_expl}. \end{proof} Let $\omega(n,k)$ denote the number of distinct prime factors of $n$ which do not divide $k$. For $k=1$, $\omega(n):=\omega(n,1)$ is the number distinct factors of $n$. Also, let $\tau^*(n,k)$ denote the number of unitary divisors of $n$ which are relatively prime to $k$. Here $\tau^*(n):=\tau^*(n,1)$ is the number of unitary divisors of $n$. We have $\tau^*(n,k)=2^{\omega(n,k)}$ and $\tau^*(n)=2^{\omega(n)}$. Another representation of $\widetilde{P}$ is given by \begin{prop} \label{prop_2} For every $n\ge 1$, \begin{equation*} \widetilde{P}(n)=\sum_{de=n}\mu(d)e\cdot 2^{\omega(e,d)}. %\label{gcd-sum_regular_convo2} \end{equation*} \end{prop} \begin{proof} By Proposition \ref{prop_1}, \begin{align*} \widetilde{P}(n)=\sum_{\substack{de=n\\(d,e)=1}} d\phi(e) = \sum_{\substack{de=n\\(d,e)=1}} d \sum_{ab=e} \mu(a)b = \sum_{\substack{dab=n\\(d,a)=1\\(d,b)=1}} d \mu(a) b \\ = \sum_{ac=n} \mu(a)c \sum_{\substack{bd=c\\(b,d)=1\\(d,a)=1}} 1 =\sum_{ac=n} \mu(a)c \, \tau^*(c,a). \end{align*} \end{proof} \begin{prop} \label{prop_ineq} For every $n\ge 1$ we have $\widetilde{P}(n) \le P(n)$, with equality iff $n$ is square-free, and $2^{\omega(n)}\phi(n)\le \widetilde{P}(n)\le 2^{\omega(n)}n$, with equality iff $n=1$. \end{prop} \begin{proof} This follows at once by \eqref{gcd-sum_regular}, \eqref{gcd-sum} and \eqref{gcd-sum_regular_expl}. \end{proof} \begin{rem}\upshape Let $\ds \widehat{P}(n):=\sum_{k\in \Reg_n} \lcm [k,n]$. Then it follows, similar to the ``usual'' lcm-sum function that for every $n\ge 1$, \begin{equation*} \widehat{P}(n)=\frac{n}{2}\left(1+\sum_{d\mid \mid n} d\phi(d)\right). \end{equation*} \end{rem} \begin{rem}\upshape For every $n\in \N$ let $A(n)$ be an arbitrary nonempty subset of the set of positive divisors of $n$. For the system of divisors $A=(A(n): n\in \N)$ and for an arbitrary arithmetical function $f$ consider the following restricted summation of the gcd's: \begin{equation*} P_{A,f}(n)= \sum_{\substack{1\le k\le n\\ \gcd (k,n)\in A(n)}} f(\gcd (k,n)). \end{equation*} It follows, similar to the proof of Proposition \ref{prop_1}, that \begin{equation*} P_{A,f}(n)= \sum_{d\in A(n)} f(d) \phi(n/d). \end{equation*} If $A(n)$ is the set of all (positive) divisors of $n$, then we have the function \eqref{gcd-sum_f} and if $A(n)$ is the set of the unitary divisors of $n$, then we reobtain \eqref{gcd-sum_regular_convo1}. If $A$ is a regular system of divisors of Narkiewicz-type, including the previous two special cases, then $P_{A,f}$ is the $A$-convolution of the functions $f$ and $\phi$. It turns out, that $P_{A,f}$ is multiplicative provided $f$ is multiplicative, cf.\ \cite[Ch.\ 4]{McC1986}. Other special cases for $A$ can also be considered, for ex. $A(n)$ the set of prime divisors of $n$ or $A(n)$ the set of exponential divisors of $n$. \end{rem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Asymptotic properties} \begin{thm} The minimal order of $\widetilde{P}(n)$ is $3n/2$ and the maximal order of $\log(\widetilde{P}(n)/n)$ is $\log 2 \log n/\log \log n$. \end{thm} \begin{proof} From \eqref{gcd-sum_regular_expl} we have $\widetilde{P}(n)\ge n(3/2)^{\omega(n)}\ge 3n/2$ for every $n\ge 1$, with equality for $n=2^{\nu}$ ($\nu \ge 1$), giving the minimal order of $\widetilde{P}(n)$. For the maximal order take into account \eqref{gcd-sum_maximal}, where the limsup is attained for a sequence of square-free integers (more exactly for $n_k= \prod_{k/\log^2 k0$, \begin{align} \sum_{n\le x} 2^{\omega(n,k)} = \frac{kx}{\zeta(2)\psi(k)}\left(\log x+ \alpha(k)-2\beta(k) + 2\gamma -1 -\frac{2\zeta'(2)}{\zeta(2)}\right) \nonumber \\ + {\cal O}\left(\sigma'_{-1+\varepsilon}(k)\sigma'_{-\theta}(k) x^{1/2}\delta(x)\right), \label{2^omega} \end{align} the ${\cal O}$ estimate being uniform in $x$ and $k$. If RH is true, then $x^{1/2}\delta(x)$ in the error term of \eqref{2^omega} can be replaced by $x^{(2-\theta)/(5-4\theta)} \eta(x)$. \end{lemma} Note that \begin{equation} \alpha(n)={\cal O}(\log n), \ \ \beta(n)={\cal O}(1), \label{error} \end{equation} since $\ds \alpha(n)\le \sum_{p\mid n} \log p= \log \gamma(n)\le \log n$ and $\ds \beta(n)\ll \sum_{p\mid n} \frac{\log p}{p^2}\le \sum_p \frac{\log p}{p^2}<\infty$. \begin{lemma} \label{lemma_n2^omega} For every $\varepsilon>0$, \begin{align} \sum_{n\le x} 2^{\omega(n,k)}n = \frac{kx^2}{2\zeta(2)\psi(k)}\left(\log x+ \alpha(k)-2\beta(k)+ 2\gamma -\frac1{2} -\frac{2\zeta'(2)}{\zeta(2)}\right) \nonumber \\ + {\cal O}\left(\sigma'_{-1+\varepsilon}(k)\sigma'_{-\theta}(k) x^{3/2}\delta(x)\right), \label{n2^omega} \end{align} If RH is true, then $x^{3/2}\delta(x)$ in the error term of \eqref{n2^omega} can be replaced by $x^{(7-5\theta)/(5-4\theta)} \eta(x)$. \end{lemma} \begin{proof} By partial summation from Lemma \ref{lemma_2^omega}. \end{proof} We can now complete the proof of Theorem 2. By Proposition \ref{prop_2} and Lemma \ref{lemma_n2^omega}, \begin{equation} \sum_{n\le x} \widetilde{P}(n)= \sum_{d\le x} \mu(d) \sum_{e\le x/d} 2^{\omega(e,d)} e \nonumber \end{equation} \begin{align*} = \frac{x^2}{2\zeta(2)} \left( \sum_{d\le x} \frac{\mu(d)}{d\psi(d)} \left(\log x+2\gamma-\frac1{2}-\frac{2\zeta'(2)}{\zeta(2)} \right)- \sum_{d\le x} \frac{\mu(d)(\log d-\alpha(d)+2\beta(d))}{d\psi(d)}\right) \nonumber \\ + {\cal O} \left(\sum_{d\le x} \sigma'_{-1+\varepsilon}(d)\sigma'_{-\theta}(d) (x/d)^{3/2} \delta(x/d)\right). \end{align*} For every $\varepsilon>0$ and $x$ sufficiently large, $x^{\varepsilon}\delta(x)$ is increasing, therefore \begin{equation*} (x/d)^{3/2} \delta(x/d)= (x/d)^{3/2-\varepsilon} (x/d)^{\varepsilon} \delta(x/d)\le (x/d)^{3/2-\varepsilon} x^{\varepsilon} \delta(x)= x^{3/2} \delta(x)/d^{3/2-\varepsilon}. \end{equation*} Furthermore, it is enough to use the inequalities $\sigma'_{-1+\varepsilon}(d)\le \tau(d)$ (for $\varepsilon<1$) and $\sigma'_{-\theta}(d)\le \tau(d)$ and then obtain the given formula using \eqref{error} and the well known estimates \begin{equation*} \sum_{d>x} \frac1{d^2}\ll \frac1{x}, \ \ \sum_{d>x} \frac{\log d}{d^2}\ll \frac{\log x}{x}. \end{equation*} If we assume RH and in the error term use the property that $\eta(x)$ is increasing, so $\eta(x/d)\le \eta(x)$ for $d\ge 1$. \end{proof} \section{Acknowledgement} The author thanks the referee for helpful suggestions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{99} \bibitem{Bor2007a} O. Bordell\`{e}s, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles/bordelles90.html} {A note on the average order of the gcd-sum function}, {\it J. Integer Sequences} {\bf 10} (2007), Article 07.3.3. \bibitem{Bor2007b} O. Bordell\`{e}s, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles2/bordelles61.pdf} {Mean values of generalized gcd-sum and lcm-sum functions}, {\it J. Integer Sequences} {\bf 10} (2007), Article 07.9.2. \bibitem{Bro2001} K. Broughan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/BROUGHAN/gcdsum.pdf} {The gcd-sum function}, {\it J. Integer Sequences} {\bf 4} (2001), Article 01.2.2. \bibitem{Bro2007} K. Broughan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Broughan/broughan1.html} {The average order of the Dirichlet series of the gcd-sum function}, {\it J. Integer Sequences} {\bf 10} (2007), Article 07.4.2. \bibitem{Ces1885} E. Ces\`{a}ro, \'Etude moyenne du plus grand commun diviseur de deux nombres, {\it Ann. Mat. Pura. Appl.} (1) {\bf 13} (1885), 235--250. \bibitem{ChiSit1985} J. Chidambaraswamy, R. Sitaramachandrarao, Asymptotic results for a class of arithmetical functions, {\it Monatsh. Math.} {\bf 99} (1985), 19--27. \bibitem{Dic1971} L. E. Dickson, {\it History of the Theory of Numbers}, vol. I, Chelsea, New York, 1971. \bibitem{Fin2003} S. R. Finch, {\it Mathematical Constants}, Cambridge University Press, 2003. \bibitem{Kap1972} I. Kaplansky, {\it Fields and Rings}, University of Chicago Press, 1972. \bibitem{McC1986} P. J. McCarthy, {\it Introduction to Arithmetical Functions}, Springer, 1986. \bibitem{Pil1933} S. S. Pillai, On an arithmetic function, {\it J. Annamalai Univ.} {\bf 2} (1933), 243--248. \bibitem{SurSiv1973} D. Suryanarayana, V. Siva Rama Prasad, The number of $k$-free and $k$-ary divisors of $m$ which are prime to $n$. {\it J. Reine Angew. Math.} 264 (1973), 56--75. \bibitem{TanZha2008} Y. Tanigawa, W. Zhai, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Tanigawa/tanigawa12.pdf} {On the gcd-sum function}, {\it J. Integer Sequences} {\bf 11} (2008), Article 08.2.3. \bibitem{Tot1998} L. T\'oth, A generalization of Pillai's arithmetical function involving regular convolutions, {\it Acta Math. Inform. Univ. Ostraviensis} {\bf 6} (1998), 203--217, available at \url{http://www.ttk.pte.hu/matek/ltoth/TothGeneralizationPillai(1998).pdf} \bibitem{Tot2008} L. T\'oth, Regular integers (mod $n$), {\it Annales Univ. Sci. Budapest., Sect. Comp.} {\bf 29} (2008), 263--275, available at \url{http://front.math.ucdavis.edu/0710.1936} \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11A25; Secondary 11N37. \noindent \emph{Keywords:} regular integers (mod $n$), gcd-sum function, unitary divisor, Dirichlet divisor problem, Riemann hypothesis. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A055653}, \seqnum{A018804}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 6 2008; revised version received January 21 2009. Published in {\it Journal of Integer Sequences}, February 13 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}