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

\usepackage{enumerate}

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

\DeclareMathOperator\Rea{Re}
\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 
A Generalization of the Gcd-Sum Function
}
\vskip 1cm
\large
Ulrich Abel, Waqar Awan, and Vitaliy Kushnirevych \\
Fachbereich MND\\
Technische Hochschule Mittelhessen\\
University of Applied Sciences\\
Wilhelm-Leuschner-Stra\ss{}e 13 \\
61169 Friedberg\\
Germany\\
\href{mailto:Ulrich.Abel@mnd.thm.de}{\tt Ulrich.Abel@mnd.thm.de}\\
\href{mailto:Waqar.Awan@stud.h-da.de}{\tt Waqar.Awan@stud.h-da.de}\\
\href{mailto:Vitaliy.Kushnirevych@mnd.thm.de}{\tt Vitaliy.Kushnirevych@mnd.thm.de}
\end{center}

\vskip .2 in


\newcommand{\Prod}{\displaystyle\prod\limits}
\newcommand{\Sum}{\displaystyle\sum\limits}



\begin{abstract}
In this paper we consider the generalization $G_{d}(n)$ of the
Broughan gcd-sum function, i.e., the sum of such gcd's that are divisors of
the positive integer $d$. Examples of Dirichlet series and asymptotic
relations for $G_{d}$ and related functions are given.
\end{abstract}


\section{Introduction}

In the recent article \cite{Broughan-2001}, Broughan studies the sum of the
greatest common divisors of the first $n$ positive integers with $n$, i.e.,
the arithmetic function
\begin{equation*}
G(n):=\Sum_{k=1}^{n}\gcd (k,n).
\end{equation*}
This function arises in deriving asymptotic estimates for a lattice point
counting problem \cite[Sect.\ 5]{Broughan-2001}. The function $G$ has
polynomial growth as $n$ tends to infinity. For $p\in \mathbb{P}$
(throughout the paper $\mathbb{P}$ denotes the set of prime numbers) and $\alpha \in \mathbb{N}$, it is not difficult to show that
\begin{equation*}
G(p^{\alpha })=\Sum_{j=0}^{\alpha -1}\underbrace{(p-1)p^{\alpha -1-j}}_{\text{number of $\gcd $'s equal to $p^{j}$}}p^{j}+1\cdot p^{\alpha }=(\alpha +1)p^{\alpha }-\alpha p^{\alpha -1}.
\end{equation*}
(cf.\ \cite[Th.\ 2.2]{Broughan-2001}). Following \cite[Cor.\ 2.1]{Broughan-2001}
$G$ is a multiplicative function, i.e., $G(mn)=G(m)G(n)$ for coprime $m,n\in
\mathbb{N}$, that is, $\gcd (m,n)=1$. The corresponding Dirichlet series $\mathcal{G}\left( s\right) $ converges at all points of the complex plane,
except at the zeros of the Riemann zeta function and the point $s=2$, where
it has a double pole. Moreover, Broughan derives asymptotic expressions for
the partial sums of the Dirichlet series at all real values of $s$.

The following generalization of $G$ (see \cite{Awan-2012}) arises in the study of distribution of determinant values in residue class rings.

For $d\in \mathbb{N}$, we introduce the function
\begin{equation*}
G_{d}(n):=\Sum_{\substack{ k=1  \\ \gcd (k,n)\mid d}}^{n}\gcd (k,n).
\end{equation*}
Obviously, $G(n)=G_{n}(n)$ and $G_{1}(n)=\varphi (n)$, where $\varphi $ is
Euler's totient function.

The purpose of this note is to study the function $G_{d}$. In the next
section we present some elementary properties of $G_{d}$. Furthermore, we
study the corresponding Dirichlet series $\mathcal{G}_{d}\left( s\right)$.
Some of the results will be applied in a forthcoming paper on the
distribution of determinant values in residue class rings and finite fields.
As an example we mention that in the residue class ring $\mathbb{Z}_{n}$ $\left( n\in \mathbb{N}\right) $, for $r\in \mathbb{Z}_{n}$,
\begin{equation*}
H_{n}(r)=|\{(i,j)\in \mathbb{Z}_{n}\times \mathbb{Z}_{n}\mid i\cdot j=r\}|,
\end{equation*}
the number of products equal to $r$ having precisely two factors in $\mathbb{Z}_{n}$, is equal to
\begin{equation*}
H_{n}(r)=
\begin{cases}
G_{n}(n)=G(n), & \text{if $r=0$}; \\
G_{d}(n)=G_{\gcd (r,n)}(n), & \text{if $r\neq 0$}.
\end{cases}
\end{equation*}

A similar problem as the calculation of the value $H_n(r)$ in the domain of positive integers is the so-called multiplication table problem posed by Erd\H{o}s (see \cite{Erdos1955}): how many integers can be written as a product $i\cdot j$ for a given positive integer $n\in\mathbb N$ with positive integers $i\leqslant n$ and $j\leqslant n$? Erd\H{o}s (\cite{Erdos1955, Erdos1960}) gave the first estimates of this quantity. Tenenbaum \cite{Tenenbaum} had made the results of Erd\H{o}s more precise. Ford (\cite{Ford2008-1, Ford2008-2}) derived the exact order of magnitude  of the $n\times n$ multiplication table size completely.
Koukoulopolous \cite{Kou2010-1, Kou2013-2} presents a perfect overview of the actual situation and the further development of Ford-Erd\H{o}s results.


\section{Properties of \texorpdfstring{$G_d$}{}}

The following lemma gathers some elementary properties of $G_{d}(n)$.

\begin{lemma}
\label{lemma1}~

\begin{enumerate}
\item[(i)] \label{erste-eigenschaft} For $m,n\in \mathbb{N}$, we have $G_{m}(n)=G_{\gcd (m,n)}(n)$.\newline
In particular, for $m,\alpha \in \mathbb{N}$, $p\in \mathbb{P}$, we have $G_{\gcd \left( m,p^{\alpha }\right) }(p^{\alpha })=G_{m}(p^{\alpha })$;
\item[(ii)] \label{Gd-und-euler} for coprime $d,n\in \mathbb{N}$, we have $G_{d}(n)=\varphi (n)$;
\item[(iii)] \label{G-d1d2} for $d=d_{1}d_{2}$ with $\gcd (d_{1},n)=1$, we have
$G_{d}(n)=G_{d_{2}}(n)$.
\end{enumerate}
\end{lemma}

\begin{proof}

\begin{enumerate}[(i)]
\item Since $\gcd (k,n)\mid \gcd (m,n)\iff \gcd (k,n)\mid m$ for all $m,n,k\in \mathbb{N}$, the first formula follows from the definition. One
obtains the second one by substituting $n=p^{\alpha }$.
\item If $\gcd (d,n)=1$, using (i) we get
\begin{equation*}
G_{d}(n)=G_{1}(n)=\varphi (n).
\end{equation*}
\item Since $\gcd (d_{1},n)=1\Rightarrow \gcd (d_{1}d_{2},n)=\gcd
(d_{2},n)$, it follows that
\begin{equation*}
G_{d}(n)=G_{d_{1}d_{2}}(n)=G_{\gcd (d_{1}d_{2},n)}(n)=G_{\gcd
(d_{2},n)}(n)=G_{d_{2}}(n),
\end{equation*}
where we used (i) twice.
\end{enumerate}
The proof of the lemma is completed.
\end{proof}

Let $\rho _{d}$ denote the multiplicative function
\begin{equation*}
\rho _{d}(w)=
\begin{cases}
w, & \text{if } w\mid d; \\
0, & \text{if } w\nmid d.
\end{cases}
\end{equation*}
Then we have the representation
\begin{equation}
G_{d}=\rho _{d}\ast \varphi ,  \label{gd=rho*phi}
\end{equation}
where $\ast $ denotes Dirichlet product. Indeed,
\begin{equation*}
G_{d}(n)=\Sum_{\substack{ k=1  \\ \gcd (k,n)\mid d}}
^{n}\gcd (k,n)=\Sum_{\substack{ w\mid d  \\ w\mid n}}
w\varphi \left( \frac{n}{w}\right) =\Sum_{w\mid n}\rho
_{d}(w)\varphi \left( \frac{n}{w}\right) =(\rho _{d}\ast \varphi )(n).
\end{equation*}
Therefore, $G_{d}$ is multiplicative as it is the Dirichlet product of multiplicative
functions \cite[Th.\ 2.5(c) and Th.\ 2.14]{Apostol}.

\begin{theorem}
\label{Gd-mult}$G_{d}$ is a multiplicative function, i.e., for coprime $m,n\in \mathbb{N}$, we have
\begin{equation*}
G_{d}(mn)=G_{d}(m)G_{d}(n).
\end{equation*}
\end{theorem}

We also give a direct proof of the preceding theorem.

\begin{proof}
\label{Gd-mult-beweis}Let $d\mid n_{1}n_{2}$ with coprime $n_{1},n_{2}\in
\mathbb{N}$. This implies $d=d_{1}d_{2}$ with $d_{1}\mid n_{1}$ and $d_{2}\mid n_{2}$, so that $d_{1}$ and $d_{2}$ are coprime. One has
\begin{equation*}
G_{d}(n_{1}n_{2})=G_{d_{1}d_{2}}(n_{1}n_{2})=
 \Sum_{w\mid d_{1}d_{2}}w\varphi \left( \frac{n_{1}n_{2}}{w}\right) =\Sum_{w_{1}\mid d_{1}}\Sum_{w_{2}\mid d_{2}}w_{1}w_{2}\varphi \left( \frac{n_{1}n_{2}}{w_{1}w_{2}}\right).
\end{equation*}
Because $\varphi $ is multiplicative and $\gcd \left( \frac{n_{1}}{w_{1}},
\frac{n_{2}}{w_{2}}\right) =1$, one obtains
\begin{equation*}
G_{d}(n_{1}n_{2}) =\Sum_{w_{1}\mid d_{1}}w_{1}\varphi
\left( \frac{n_{1}}{w_{1}}\right) \Sum_{w_{2}\mid
d_{2}}w_{2}\varphi \left( \frac{n_{2}}{w_{2}}\right) =
G_{d_{1}}\left( n_{1}\right) G_{d_{2}}\left( n_{2}\right) =G_{d}\left(
n_{1}\right) G_{d}\left( n_{2}\right) .
\end{equation*}
This completes the proof.
\end{proof}

\begin{theorem}
\label{Gd-d-mult} For $n\in \mathbb{N}$ and for coprime $d_{1},d_{2}\in
\mathbb{N}$, we have
\begin{equation*}
G_{d_{1}}(n)\cdot G_{d_{2}}(n)=\varphi (n)\cdot G_{d_{1}d_{2}}(n).
\end{equation*}
In particular, $G_{d_{1}d_{2}}(n)\mid G_{d_{1}}(n)G_{d_{2}}(n)$.
\end{theorem}

\begin{proof}
Let $d=d_{1}d_{2}$ with $\gcd (d_{1},d_{2})=1$. By Equation \eqref{gd=rho*phi} we have
\begin{equation*}
G_{d}(n)=(\rho_{d}\ast\varphi )(n)=\Sum_{w\mid n}\rho_{d_{1}d_{2}}(w)\varphi\left( \frac{n}{w}\right)
=\Sum_{w_{1}\mid n}\Sum_{w_{2}\mid
n}\rho_{d_{1}}(w_{1})\rho _{d_{2}}(w_{2})\varphi \left( \frac{n}{w_{1}w_{2}}
\right).
\end{equation*}
Now, decompose $n=kn_{1}n_{2}$ in a product of three pairwise coprime
factors $k$, $n_{1}$, $n_{2}$ such that $d_{i}\mid n_{i}$ $\left(
i=1,2\right) $. If $w_{i}\mid d_{i}$ $\left( i=1,2\right) $ we conclude that
\begin{equation*}
\varphi \left( \frac{n}{w_{1}w_{2}}\right) =\varphi (k)\varphi \left(
\frac{n_{1}}{w_{1}}\right) \varphi \left( \frac{n_{2}}{w_{2}}\right)
 =\varphi (k)\;\dfrac{\varphi \left( \frac{n}{w_{1}}\right) \varphi \left(
\frac{n}{w_{2}}\right) }{\varphi (kn_{2})\varphi (kn_{1})}=\dfrac{\varphi
\left( \frac{n}{w_{1}}\right) \varphi \left( \frac{n}{w_{2}}\right)}{\varphi (n)}.
\end{equation*}
Hence, we obtain
\begin{equation*}
\varphi \left( n\right) G_{d}(n)=\Sum_{w_{1}\mid n}\rho
_{d_{1}}(w_{1})\varphi \left( \frac{n}{w_{1}}\right) \Sum_{w_{2}\mid
n}\rho _{d_{2}}(w_{2})\varphi \left( \frac{n}{w_{2}}\right)
=G_{d_{1}}(n)\cdot G_{d_{2}}(n)
\end{equation*}
which is the desired formula.
\end{proof}

We close this section with the following nice formula.

\begin{theorem}
For all $n\in \mathbb{N}$, we have
\begin{equation*}
\Sum_{i=1}^{n}G_{i}(n)=n^{2}.
\end{equation*}
\end{theorem}

\begin{proof}
Analogously to the proof of Theorem~\ref{Gd-mult} one has
\begin{align*}
\Sum_{i=1}^{n}G_{i}(n)& =
\Sum_{i=1}^{n}\Sum_{w\mid n}\rho _{i}(w)\varphi
\left( \frac{n}{w}\right) =\Sum_{w\mid n}\varphi \left(
\frac{n}{w}\right) \Sum_{i=1}^{n}\rho _{i}(w) \\
& =\Sum_{w\mid n}\varphi \left( \frac{n}{w}\right) w
\Sum_{\substack{ 1\leqslant i\leqslant n  \\ w\mid i}}1=
\Sum_{w\mid n}\varphi \left( \frac{n}{w}\right) w\frac{n}{w}=n\Sum_{w\mid n}\varphi \left( w\right) =n^{2},
\end{align*}
where we used that $\Sum_{w\mid n}\varphi \left(
w\right) =n$.
\end{proof}

\section{Evaluation of \texorpdfstring{$G_d$}{} at positive integers}

In this section we consider the problem how to calculate the values of $G_{d}(n)$ for positive integers. We start with the special case of prime
powers. In the following $\delta _{\alpha \beta }$ denotes the Kronecker
symbol defined by $\delta_{\alpha\beta}=\begin{cases} 1, &\text{if $\alpha=\beta$};\\
0, &\text{otherwise}.\end{cases}$

\begin{proposition}
\label{prop-Gd-fuer-palpha} For prime powers $n=p^{\alpha }$ ($\alpha \in
\mathbb{N}$) and $d=p^{\beta }$, $\beta \leqslant \alpha $ ($\beta \in
\mathbb{N}\cup \{0\}$), we have
\begin{equation*}
G_{p^{\beta }}(p^{\alpha })=\varphi (p^{\alpha })\left( 1+\beta +\dfrac{\delta _{\alpha \beta }}{p-1}\right).
\end{equation*}
For prime powers $n=p^{\alpha }$ ($\alpha \in \mathbb{N}$) and $d=p^{\beta }$, $\beta >\alpha $ ($\beta \in \mathbb{N}$), we have
\begin{equation*}
G_{p^{\beta }}(p^{\alpha })=G_{p^{\alpha }}(p^{\alpha })=\varphi (p^{\alpha
})\left( 1+\alpha +\dfrac{1}{p-1}\right).
\end{equation*}
\end{proposition}

\begin{proof}
For $0<\beta <\alpha $, we have
\begin{equation*}
G_{p^{\beta }}(p^{\alpha })=\Sum_{j=0}^{\beta
}(p^{\alpha -j}-p^{\alpha -j-1})p^{j}=(p^{\alpha }-p^{\alpha -1})(1+\beta
)=\varphi (p^{\alpha })(1+\beta ),
\end{equation*}
and, for $\beta =\alpha $,
\begin{align*}
G_{p^{\beta }}(p^{\alpha })& =G_{p^{\alpha }}(p^{\alpha })=G(p^{\alpha
})=(\alpha +1)p^{\alpha }-\alpha p^{\alpha -1} \\
& =(\alpha +1)(p^{\alpha }-p^{\alpha -1})+p^{\alpha -1}=\varphi (p^{\alpha
})(1+\beta )+p^{\alpha -1}.
\end{align*}
In the case $\beta =0$ application of Lemma~\ref{lemma1} (ii) leads to $
G_{1}(p^{\alpha })=\varphi (p^{\alpha })=\varphi (p^{\alpha })(1+\beta )$.
Thus, for all $0\leqslant \beta \leqslant \alpha $, one has
\begin{equation*}
G_{p^{\beta }}(p^{\alpha })=\varphi (p^{\alpha })(1+\beta )+p^{\alpha
-1}\cdot \delta _{\alpha \beta }=\varphi (p^{\alpha })\left( 1+\beta +\dfrac{
p^{\alpha -1}\cdot \delta _{\alpha \beta }}{\varphi (p^{\alpha })}\right) .
\end{equation*}
Taking into account that $\varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}$
one obtains the first result. \newline
For $\beta >\alpha $, we have $\gcd (k,p^{\alpha })\mid p^{\beta }\iff \gcd
(k,p^{\alpha })\mid p^{\alpha }$. Hence,
\begin{equation*}
G_{p^{\beta }}(p^{\alpha })=\Sum_{\substack{ k=1  \\
\gcd (k,p^{\alpha })\mid p^{\beta }}}^{p^{\alpha }}\gcd (k,p^{\alpha })=
\Sum_{\substack{ k=1  \\ \gcd (k,p^{\alpha })\mid
p^{\alpha }}}^{p^{\alpha }}\gcd (k,p^{\alpha })=G_{p^{\alpha }}(p^{\alpha })
\end{equation*}
and the second result follows by application of the first formula.
\end{proof}

\begin{remark}
\label{rem2} The result of Proposition~\ref{prop-Gd-fuer-palpha} can be
written in one single formula: for $p\in \mathbb{P}$, $\alpha \in \mathbb{N}$
and $\beta \in \mathbb{N}\cup \{0\}$, we have
\begin{equation*}
G_{p^{\beta }}(p^{\alpha })=\varphi (p^{\alpha })\left( 1+\min (\alpha
,\beta )+\dfrac{\delta _{\alpha ,\min (\alpha ,\beta )}}{p-1}\right) .
\end{equation*}
\end{remark}

\begin{theorem}
\label{Gd-als-ProduktVers1} For $n\in \mathbb{N}$ with prime powers
decomposition $n=p_{1}^{\lambda _{1}}\cdot \ldots \cdot p_{t}^{\lambda _{t}}$ and
positive integer $d=c\cdot p_{1}^{\kappa _{1}}\cdots
p_{t}^{\kappa _{t}}$ with $p_{j}\nmid c$ for all $j=1,\dots ,t$, and $0\leqslant \kappa _{j}$ we have the representation\footnote{$\kappa _{j}=0$ means that $p_{j}$ is
not present in the decomposition of $d$, i.e., $p_{j}\nmid d$.}
\begin{equation*}
G_{d}(n)=\varphi (n)\cdot \Prod_{j=1}^{t}\left( 1+\min
(\kappa _{j},\lambda _{j})+\delta _{\lambda _{j},\min (\kappa _{j},\lambda _{j})}
\dfrac{1}{p_{j}-1}\right) .
\end{equation*}
\end{theorem}

\begin{proof}
Because $G_{d}$ is multiplicative, by Theorem~\ref{Gd-mult}, and applying
Lemma~\ref{lemma1}~(iii), we obtain
\begin{align*}
G_{d}(n)& =G_{d}\left( \Prod_{j=1}^{t}p_{j}^{\lambda
_{j}}\right) \\
& =\Prod_{j=1}^{t}G_{c\cdot p_{1}^{\kappa _{1}}\cdots p_{t}^{\kappa _{t}}}\left( p_{j}^{\lambda _{j}}\right) \\
& =\Prod_{j=1}^{t}G_{p_{j}^{\kappa _{j}}}\left(
p_{j}^{\lambda _{j}}\right) \\
& =\Prod_{j=1}^{t}\varphi \left( p_{j}^{\lambda _{j}}\right)
\left( 1+\min (\kappa _{j},\lambda _{j})+\dfrac{\delta _{\lambda _{j}\min (\kappa
_{j},\lambda _{j})}}{p_{j}-1}\right) ,
\end{align*}
where the last equation is a consequence of Rem.\ \ref{rem2}.
\end{proof}

We note that under the notation of Theorem~\ref{Gd-als-ProduktVers1} the
equation
\begin{equation*}
\gcd (d,n)=p_{1}^{\kappa _{1}}\cdots p_{t}^{\kappa _{t}}
\end{equation*}
defines unique numbers $\kappa _{j}$ ($j=1,\dots ,t$) with $0\leqslant
\kappa _{j}\leqslant \lambda _{j}$, such that the result can be written in the
form
\begin{equation*}
G_{d}(n)=G_{\gcd (d,n)}(n)=\varphi (n)\cdot \Prod_{j=1}^{t}\left( 1+\kappa _{j}+\delta _{\lambda _{j},\kappa _{j}}\dfrac{1}{p_{j}-1}\right) .
\end{equation*}

\section{Dirichlet series, averages and asymptotic properties}

Some asymptotic formulas of the Broughan's gcd-sum function were derived by Broughan \cite{Broughan-2001} and Bordell\`es \cite{Bordelles-2012}. The average order of the Dirichlet series of the Broughan's gcd-sum function was studied by  Broughan \cite{Broughan-2007} and Bordell\`es \cite{Bordelles-2007}. In this section we give some examples of Dirichlet series of arithmetic functions
connected with $G_{d}(n)$. We calculate the average functions and derive some asymptotic formulas for these examples.

The Dirichlet series for an arithmetic function $f(n)$ is defined (see,
e.g., \cite[11.1, p.\ 224]{Apostol}) by
\begin{equation*}
\mathcal{F}(s):=\Sum_{n=1}^{\infty }\dfrac{f(n)}{n^{s}}.
\end{equation*}
The most prominent example is the Riemann $\zeta $ function $\zeta (s)=
\Sum_{n=1}^{\infty }\dfrac{1}{n^{s}}$. It is clear, that
$\zeta (s)$ is the Dirichlet series associated to $f(n)=1$, for all $n\in
\mathbb{N}$.

For any prime number $p$, the Bell series \cite[Sect.\ 2.15, p.\ 42ff]{Apostol}
of an arithmetic function $f$ is the formal power series
\begin{equation*}
f_{p}(x)=\Sum_{n=0}^{\infty }f(p^{n})x^{n}.
\end{equation*}
If $f$ is multiplicative the corresponding Dirichlet series is given by
\begin{equation*}
\mathcal{F}(s)=\Sum_{n=1}^{\infty }f(n)n^{-s}=
\Prod_{p}f_{p}(p^{-s})
\end{equation*}
provided that the Dirichlet series converges absolutely for $\Rea s>a$
(see, e.g., \cite[Th.\ 11.7, p.\ 231]{Apostol}).

The number $e\in \mathbb{N}\cup \{0\}$ is called the \emph{$m$-adic order of $n\in \mathbb{N}$} ($m\in \mathbb{N}$), if $m^{e}\mid n$ and $m^{e+1}\nmid n$. It is denoted by $e=\nu_m(n)$.

\subsection{The arithmetic function \texorpdfstring{$G_d$}{}}

\subsubsection{Dirichlet series}

Since $G_{d}=\rho _{d}\ast \varphi $ (see (\ref{gd=rho*phi})) and
\begin{align*}
\mathcal{P}_{d}(s)& :=\Sum_{n=1}^{\infty }\dfrac{\rho
_{d}(n)}{n^{s}}=\Sum_{n\mid d}\dfrac{1}{n^{s-1}}; \\
\Phi (s)& :=\Sum_{n=1}^{\infty }\dfrac{\varphi (n)}{n^{s}}
=\dfrac{\zeta (s-1)}{\zeta (s)}=\Prod_{p}\dfrac{1-p^{-s}
}{1-p^{1-s}},
\end{align*}
(\cite[Ex.\ 4, p.\ 229 and p.\ 231]{Apostol}), we have according to \cite[Th.
11.5]{Apostol}: for $\Rea s>2$,
\begin{equation*}
\mathcal{G}_{d}(s):=\Sum_{n=1}^{\infty }\dfrac{G_{d}(n)}{n^{s}}=\Sum_{n=1}^{\infty }\dfrac{\rho _{d}(n)\ast
\varphi (n)}{n^{s}}=\mathcal{P}_{d}(s)\Phi (s),
\end{equation*}
so
\begin{equation*}
\mathcal{G}_{d}(s)=\dfrac{\zeta (s-1)}{\zeta (s)}\cdot
\Sum_{n\mid d}\dfrac{1}{n^{s-1}}=\Prod_{p}\dfrac{
1-p^{-s}}{1-p^{1-s}}\cdot \Sum_{n\mid d}\dfrac{1}{n^{s-1}}.
\end{equation*}
If $d=1$ one obviously has $\mathcal{G}_{1}(s)=\dfrac{\zeta (s-1)}{\zeta (s)}
$ (cf.\ \cite[Ex.\ 3, p.\ 231]{Apostol}). For $d\in \mathbb{P}$, one has
\begin{equation*}
\mathcal{G}_{d}(s)=\dfrac{\zeta (s-1)}{\zeta (s)}\left( 1+\dfrac{1}{d^{s-1}}
\right) .
\end{equation*}

\subsubsection{Average functions}

We study the asymptotic behaviour of the average function
\begin{equation*}
\mathcal{G}_{d}^{\left[ \alpha \right] }\left( x\right) :=\sum_{n\leq
x}n^{-\alpha }G_{d}\left( n\right)
\end{equation*}
as $n$ tends to infinity. Taking advantage of the representation $G_{d}=\rho
_{d}\ast \varphi $ we obtain
\begin{equation*}
\mathcal{G}_{d}^{\left[ \alpha \right] }\left( x\right) =\sum_{n\leq
x}\sum_{w\mid n}\frac{\rho _{d}\left( w\right) }{w^{\alpha }}\frac{\varphi
\left( \frac{n}{w}\right) }{\left( \frac{n}{w}\right) ^{\alpha }}.
\end{equation*}
By application of \cite[Th.\ 3.10, p.\ 65]{Apostol}, we conclude that
\begin{equation*}
\mathcal{G}_{d}^{\left[ \alpha \right] }\left( x\right) =\sum_{n\leq
x}n^{-\alpha }\rho _{d}\left( n\right) \Phi ^{\left[ \alpha \right] }\left(
\frac{x}{n}\right) =\sum_{w\mid d}w^{-\left( \alpha -1\right) }\Phi ^{\left[
\alpha \right] }\left( \frac{x}{w}\right) ,
\end{equation*}
where $\Phi ^{\left[ \alpha \right] }$ denotes the average
\begin{equation*}
\Phi ^{\left[ \alpha \right] }\left( x\right) :=\sum_{n\leq x}n^{-\alpha
}\varphi \left( n\right)
\end{equation*}
of Euler's totient function $\varphi $. We distinguish 3 cases. Because, for
$\alpha \leq 1$,
\begin{equation*}
\Phi ^{\left[ \alpha \right] }\left( x\right) \sim \frac{x^{2-\alpha }}{
2-\alpha }\zeta ^{-1}\left( 2\right) +O\left( x^{1-\alpha }\log x\right)
\text{ \qquad }\left( x\rightarrow \infty \right) ,
\end{equation*}
(\cite[Ex.\ 8, p.\ 71]{Apostol}), we have
\begin{equation*}
\mathcal{G}_{d}^{\left[ \alpha \right] }\left( x\right) \sim \frac{
x^{2-\alpha }}{2-\alpha }\zeta ^{-1}\left( 2\right) \sum_{w\mid d}\frac{1}{w}
+O\left( x^{1-\alpha }\log x\right) \text{ \qquad }\left( x\rightarrow
\infty \right) .
\end{equation*}

Because, for $\alpha >1,\alpha \neq 2$,
\begin{equation*}
\Phi ^{\left[ \alpha \right] }\left( x\right) \sim \frac{x^{2-\alpha }}{
2-\alpha }\zeta ^{-1}\left( 2\right) +\frac{\zeta \left( \alpha -1\right) }{
\zeta \left( \alpha \right) }+O\left( x^{1-\alpha }\log x\right) \text{
\qquad }\left( x\rightarrow \infty \right) ,
\end{equation*}
(\cite[Ex.\ 7, p.\ 71]{Apostol}), we have
\begin{equation*}
\mathcal{G}_{d}^{\left[ \alpha \right] }\left( x\right) \sim \frac{
x^{2-\alpha }}{2-\alpha }\zeta ^{-1}\left( 2\right) \sum_{w\mid d}\frac{1}{w}
+\frac{\zeta \left( \alpha -1\right) }{\zeta \left( \alpha \right) }
\sum_{w\mid d}w^{-\left( \alpha -1\right) }+O\left( x^{1-\alpha }\log
x\right) \text{ \qquad }\left( x\rightarrow \infty \right) .
\end{equation*}
Finally, for $\alpha =2$, we have
\begin{equation*}
\Phi ^{\left[ 2\right] }\left( x\right) \sim \frac{\log x}{\zeta \left(
2\right) }+\frac{\gamma }{\zeta \left( 2\right) }-A+O\left( \frac{\log x}{x}
\right) \text{ \qquad }\left( x\rightarrow \infty \right) ,
\end{equation*}
where $\gamma $ is Euler's constant and $A=\sum_{n=1}^{\infty }\mu \left(
n\right) n^{-2}\log n$ (\cite[Ex.\ 6, p.\ 71]{Apostol}), and we conclude that
\begin{equation*}
\mathcal{G}_{d}^{\left[ 2\right] }\left( x\right) \sim \frac{1}{\zeta \left(
2\right) }\sum_{w\mid d}\frac{\log \left( x/w\right) }{w}+\left( \frac{
\gamma }{\zeta \left( \alpha \right) }-A\right) \sum_{w\mid d}w^{-1}+O\left(
\frac{\log x}{x}\right) \text{ \qquad }\left( x\rightarrow \infty \right) .
\end{equation*}

\subsection{The arithmetic function \texorpdfstring{$G_{n/\gcd (r,n)}(n)$}{}}

Let $r\in \mathbb{N}$ be given. Consider the arithmetic function
\begin{equation*}
b^{(r)}(n):=G_{n/\gcd (r,n)}(n).
\end{equation*}
which is easily seen to be multiplicative. Let $p$ be a prime number and put
$\beta =\nu_p(r)$. According to Prop.\ \ref{prop-Gd-fuer-palpha} one has
\begin{equation*}
b^{(r)}(p^{n})=G_{p^{n}/\gcd (r,p^{n})}(p^{n})=G_{p^{n-\beta
}}(p^{n})=\varphi (p^{n})\left( 1+n-\beta +\dfrac{\delta _{n,n-\beta }}{p-1}
\right) .
\end{equation*}
So, if $\beta =0$ one has $\delta _{n,n-\beta }=1$ and
\begin{equation*}
b^{(r)}(p^{n})=\varphi (p^{n})\left( 1+n+\frac{1}{p-1}\right)
=(n+1)p^{n}-np^{n-1}.
\end{equation*}
Therefore, for $\beta =0$, the Bell series is given by
\begin{equation*}
b_{p}^{(r)}(x)=\Sum_{n=0}^{\infty }b^{(r)}(p^{n})x^{n}=
\Sum_{n=0}^{\infty }\left( (n+1)p^{n}-np^{n-1}\right)
x^{n}=\dfrac{1-x}{(1-px)^{2}}.
\end{equation*}
If $\beta >0$ one has $\delta _{n,n-\beta }=0$ and
\begin{align*}
b_{p}^{(r)}(x)& =\Sum_{n=0}^{\infty }b^{(r)}(p^{n})x^{n}=
\Sum_{n=0}^{\infty }\varphi (p^{n})(1+n-\beta )x^{n} \\
& =\Sum_{n=0}^{\infty }(p^{n}-p^{n-1})(1+n-\beta )x^{n}=
\dfrac{(p-1)(px\beta -\beta +1)}{p(px-1)^{2}}.
\end{align*}
Hence, the Dirichlet series is given by
\begin{equation*}
\mathcal{B}^{(r)}(s):=\dfrac{\zeta ^{2}(s-1)}{\zeta (s)}\prod\limits_{p\mid r}
\dfrac{(p-1)(1-\left( 1-p^{1-s}\right) \beta \left( p\right) )}{p-p^{1-s}}
\text{ \qquad }\left( \Rea s>2\right) ,
\end{equation*}
where $\beta \left( p\right) =\nu_p(r)$.

\subsection{The arithmetic function \texorpdfstring{$G_{n}(\gcd (r,n)n)$}{}}

Let $r\in \mathbb{N}$ be given. Consider the arithmetic function
\begin{equation*}
a^{(r)}(n):=G_{n}(\gcd (r,n)\cdot n)
\end{equation*}
which is easily seen to be multiplicative. Let $p$ be a prime number and put
$\beta =\nu_p(r)$. According to Remark \ref{rem2} one has
\begin{align*}
a^{(r)}(p^{n})& =G_{p^{n}}(\gcd (r,p^{n})p^{n})=G_{p^{n}}\left( p^{n+\min
( \beta ,n) }\right)  \\
& =\varphi \left( p^{n+\min ( \beta ,n) }\right) \left(
1+n+\delta _{0,\min ( \beta ,n) }\frac{1}{p-1}\right) .
\end{align*}
If $\beta =0$, one has $\delta _{0,\min (\beta ,n)}=1$ and
\begin{equation*}
a^{(r)}(p^{n})=\varphi (p^{n})\left( 1+n+\frac{1}{p-1}\right)
=(n+1)p^{n}-np^{n-1}.
\end{equation*}
Therefore, for $\beta =0$, the Bell series is given by
\begin{equation*}
a_{p}^{(r)}(x)=\Sum_{n=0}^{\infty }a^{(r)}(p^{n})x^{n}=
\Sum_{n=0}^{\infty }\left( (n+1)p^{n}-np^{n-1}\right)
x^{n}=\dfrac{1-x}{(1-px)^{2}}.
\end{equation*}
If $\beta >0$ one has $\delta _{0,\min (\beta ,n)}=0$ and
\begin{align*}
a_{p}^{(r)}(x)& =1+\Sum_{n=1}^{\infty }(1+n)\varphi
(p^{n+\min (\beta ,n)})x^{n} \\
& =1+\Sum_{n=1}^{\beta }(1+n)\varphi (p^{2n})x^{n}+
\Sum_{n=\beta +1}^{\infty }(1+n)\varphi (p^{n+\beta
})x^{n} \\
& =1+\Sum_{n=1}^{\beta }(1+n)(p^{2n}-p^{2n-1})x^{n}+
\Sum_{n=\beta +1}^{\infty }(1+n)(p^{n+\beta }-p^{n+\beta
-1})x^{n} \\
& =1+\dfrac{p-1}{p}\Sum_{n=1}^{\beta
}(n+1)(p^{2}x)^{n}+p^{\beta -1}(p-1)\Sum_{n=\beta
+1}^{\infty }(n+1)(px)^{n} \\
& =1+\dfrac{(p-1)px((\beta +1)(p^{2}x)^{\beta +1}-(\beta +2)(p^{2}x)^{\beta
}-p^{2}x+2)}{(p^{2}x-1)^{2}} \\
& \hspace{2cm}-\dfrac{(p-1)p^{2\beta }x^{\beta +1}((\beta +1)px-(\beta +2))}{
(px-1)^{2}}.
\end{align*}
Hence, the Dirichlet series is given by
\begin{equation*}
\mathcal{A}^{(r)}(s):=\dfrac{\zeta ^{2}(s-1)}{\zeta (s)}\prod\limits_{p\mid
r}\left( \dfrac{\left( 1-p^{1-s}\right) ^{2}}{1-p^{-s}}a_{p}^{(r)}(p^{-s})
\right) \text{ \qquad }\left( \Rea s>2\right) .
\end{equation*}
where
\begin{eqnarray*}
a_{p}^{(r)}(p^{-s}) &=&1-\dfrac{(p-1)p^{2\beta }p^{-s(\beta +1)}((\beta
+1)p^{1-s}-(\beta +2))}{(1-p^{1-s})^{2}} \\
&&+\dfrac{(p-1)p^{1-s}((\beta +1)p^{(2-s)(\beta +1)}-(\beta +2)p^{(2-s)\beta
}-p^{2}x+2)}{(p^{2}x-1)^{2}}
\end{eqnarray*}
and $\beta =\beta \left( p\right) =\nu_p(r)$.

\section{Acknowledgment}

 The authors are grateful to the referee for valuable remarks, in particular for pointing out the similarity of our function $H_n(r)$ to the famous Erd\H{o}s multiplication table problem.


\begin{thebibliography}{99}
\bibitem{Apostol} T. M. Apostol, {\em Introduction to Analytic Number
Theory}, Springer, 1976.

\bibitem{Awan-2012} W. Awan, Werteverteilung der Determinanten von
Matrizen \"{u}ber Restklassenringen und endlichen K\"{o}rpern,
Bachelor thesis, Friedberg, Germany, 2012.

\bibitem{Bordelles-2007} O. Bordell\`es, A note on the average order of
the gcd-sum function, {\em J. Integer Seq.} {\bf10} (2007),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles/bordelles90.html}{Article 07.3.3}.

\bibitem{Bordelles-2012} O. Bordell\`es, An asymptotic formula for short sums of
gcd-sum functions, {\em J. Integer Seq.} {\bf15} (2012), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Bordelles/bordelles11.html}{Article 12.6.8}.

\bibitem{Broughan-2001} K. A. Broughan, The gcd-sum function,
{\em J. Integer Seq.} {\bf4} (2001),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL4/BROUGHAN/gcdsum.html}{Article 01.2.2}.

\bibitem{Broughan-2007} K. A. Broughan, The average order of the
Dirichlet series of the gcd-sum function, {\em J. Integer Seq.} {\bf10}
(2007), \href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Broughan/broughan1.html}{Article 07.4.2}.  

\bibitem{Erdos1955} P. Erd\H{o}s, Some remarks on number theory, {\em
Riveon Lematematika} {\bf9} (1955), 45--48.

\bibitem{Erdos1960} P. Erd\H{o}s, An asymptotic inequality in the theory of numbers, {\em Vestnik Leningrad Univ.} {\bf15} (1960), 41--49.

\bibitem{Ford2008-1} K. Ford, Integers with a divisor in $(y,2y]$ in
J.-M.~Koninck, A.~Granville, F.~Luca, eds., {\em Anatomy of Integers},
CRM Proc. and Lect. Notes 46, Amer. Math. Soc., Providence, RI, 2008,
pp. 65--81.

\bibitem{Ford2008-2} K. Ford, The distribution of integers with a divisor in a given interval, {\em Annals of Math.} {\bf168} (2008), 367--433.

\bibitem{Kou2010-1} D. Koukoulopolous, Generalized and restricted
multiplication tables of integers, Ph.D. thesis, Univ. Illinois, 2010,
\\ \url{http://dms.umontreal.ca/~koukoulo/documents/publications/phdthesis.pdf}.


\bibitem{Kou2013-2} D. Koukoulopolous, On the number of integers in a
generalized multiplication table, preprint,
\url{http://arxiv.org/abs/1102.3236v3}.

\bibitem{Tenenbaum} G. Tenenbaum, Sur la probabilit\'e qu'un entier
poss\`ede un diviseur dans un intervalle donn\'e, {\em Compositio
Math.} {\bf51} (1984), 243--263.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11A05;
Secondary 11A25, 11F66, 11N37, 11N56.

\noindent \emph{Keywords: } multiplicative structure, arithmetic function,
one-variable Dirichlet series, asymptotic results on arithmetic functions.

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received  February 6 2013;
revised version received  June 29 2013.
Published in {\it Journal of Integer Sequences}, July 29 2013.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.
