\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 
The Composition of the gcd and Certain \\
\vskip .1in
Arithmetic Functions
}
\vskip 1cm
\large
Olivier Bordell\`es\\
2, allie de la Combe\\
43000 Aiguilhe\\
France\\
\href{mailto:borde43@wanadoo.fr}{\tt borde43@wanadoo.fr}
\end{center}

\vskip .2 in


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

\newcommand{\N}{\mathbb {N}}
\newcommand{\Z}{\mathbb {Z}}
\newcommand{\Q}{\mathbb {Q}}
\newcommand{\R}{\mathbb {R}}
\newcommand{\C}{\mathbb {C}}
\newcommand{\K}{\mathbb {K}}


\begin{abstract}
We provide mean value results for sums of the composition of the gcd
and arithmetic functions belonging to certain classes. Some
applications are also given.
\end{abstract}


\section{Introduction}
In what follows, $f : \N \longrightarrow \C$ is an arithmetic function with Dirichlet series $F(s)$ and $\gcd(a,b)$ is the gcd of $a$ and $b$. The Dirichlet convolution product $f \star g$ of $f$ and $g$ is defined by
$$\left( f \star g \right) (n) = \sum_{d \mid n} f(d) g \left ( \frac{n}{d} \right ).$$
 The classical arithmetic functions $\tau$, $\sigma$, $\mu$, $\varphi$, $\omega$ are respectively the number and sum of divisors, the M\"obius function, the Euler totient function and the number of distinct prime factors. Finally, $\gamma$ is the Euler--Mascheroni constant, $\lfloor t \rfloor$ is the integer part of $t \in \R$ and we set $\psi(t):= t - \lfloor t \rfloor - 1/2$. 

In 1885, E. Ces\'{a}ro \cite{ces} proved the following identity.
\begin{lemma}
\label{le1}
For every positive integer $n$, we have
$$\sum_{i=1}^{n} f(\gcd(i,n)) = (f \star \varphi)(n).$$
\end{lemma}
This follows from
$$\sum_{i=1}^{n} f(\gcd(i,n)) = \sum_{d \mid n} f(d) \sum_{\substack{k \leq n/d \\ \gcd(k,n/d)=1}} 1 = \sum_{d \mid n} f(d) \varphi \left ( \frac{n}{d} \right ) = (f \star \varphi)(n).$$
It should be mentioned that such an identity also occurs with some other convolution products where the summation is over some subset of the set of the divisors of $n$. For instance, L. T\'{o}th \cite{tot} showed that
$$\sum_{i \in \mathrm{Reg}(n)} f(\gcd(i,n)) = \sum_{\substack{d \mid n \\ \gcd(d,n/d)=1}} f(d) \varphi \left ( \frac{n}{d} \right ),$$
where the notation $i \in \mathrm{Reg}(n)$ means that $1 \leq i \leq n$ and there exists an integer $x$ such that $i^2x \equiv i \pmod n$.

Lemma~\ref{le1} has a lot of interesting applications.
\begin{enumerate}
   \item[(a)] With $f = \mathrm{Id}$ we get
$$\sum_{i=1}^{n} \gcd(i,n) = (\mathrm{Id} \star \varphi)(n),$$
which is Pillai's function \cite{pil}.
   \item[(b)] With $f = \mu$ we get 

\begin{alignat}{1}
   \sum_{i=1}^{n} \mu(\gcd(i,n)) = (\mu \star \varphi)(n), \label{id:0}
\end{alignat}
and thus the number of primitive Dirichlet characters modulo $n$ is equal to $\sum_{i=1}^{n} \mu(\gcd(i,n)).$ In particular, if $m$ is an odd positive integer then  
$$\sum_{i=1}^{2m} \mu(\gcd(i,2m))=0.$$
   \item[(c)] With $f = \tau$ we have, using $\tau \star \varphi = \sigma$

\begin{alignat}{1}
   \sum_{i=1}^{n} \tau(\gcd(i,n))=\sigma(n), \label{id:1}
\end{alignat}
so that 
$$\sum_{i=1}^{n} \tau(\gcd(i,n)) \ll n \log \log n,$$
which should be compared to the classical estimate $\sum_{i =1}^{n} \tau(i) \ll n \log n.$
   \item[(d)] With $f=2^{\omega}$ we easily get

\begin{alignat}{1}
   \sum_{i=1}^{n} 2^{\omega(\gcd(i,n))} = \Psi(n), \label{id:2}
\end{alignat}
where $\Psi(n):=(\mu^2 \star \mathrm{Id})(n)=n \prod_{p \mid n} (1+p^{-1})$ is the Dedekind arithmetic function.
   \item[(e)] Applying Lemma~\ref{le1} twice with $f=\tau$ and $f = \sigma$ respectively, and using $\tau \star \varphi = \sigma$ and $\sigma \star \varphi = \mathrm{Id} \times \tau$, we obtain
$$\tau(n) = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{\gcd(i,n)} \tau(\gcd(i,j,n)).$$
\end{enumerate}
The aim of this paper is to estimate the sums

\begin{alignat}{1}
   \sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) \label{s:1}
\end{alignat}
for $x \geq 1$ sufficiently large and an arithmetic function $f$ verifying certain hypotheses. In section~\ref{t:2}, we provide a result for four classes of multiplicative functions and then give some applications in section~\ref{t:3}. The aim of section~\ref{t:4} is to provide a refinement of an estimate given in Theorem~\ref{t3}.

\section{Main result}
\label{t:2}
This section is devoted to the proof of a unified theorem which gives estimates for sums of the type (\ref{s:1}). To this end, we first need some specific notation. More precisely, we consider the four following classes of real-valued multiplicative functions.

\begin{itemize}
   \item[1.] $f \in \mathcal{M}_1(\alpha)$ if there exists a real number $\alpha \geq 0$ such that 

     \begin{alignat}{1}
         \sum_{n \leq x} \left | (f \star \mu )(n) \right | & \ll x (\log x)^{\alpha}. \label{h:11} 
     \end{alignat}

   \item[2.] $f \in \mathcal{M}_2(\alpha)$ if there exists a real number $\alpha \in [0,3/2]$ such that, for every positive integer $m$ we have
     \begin{alignat}{1}
        & \sum_{n \leq x} |(f \star \mu)(n)| = x \sum_{i=0}^{\lfloor \alpha \rfloor+m} A_i (\log x)^{\alpha -i} + O \left ( \frac{x}{(\log x)^m} \right ) \qquad (A_i \in \R). \label{h:21} \\
        & \sum_{n \leq x} ((f \star \mu)(n))^2  \ll x (\log x)^{\beta} \qquad (\beta \geq 0). \label{h:22} \\
        & f(p^l) - f(p^{l-1})  \ \text{is bounded for all\ } l \geq 1 \ \mathrm{and \ primes\ } p. \label{h:225} \\
        & \text{The sequence\ } p \longmapsto f(p)-1 \ \text{is ultimately monotone}. \label{h:23}
     \end{alignat}

   \item[3.] $f \in \mathcal{M}_3(A)$ if there exist $A > 0$, $B, \ C, \ D \in \R$ and an integrable function $R$ defined on $[1,+\infty)$ such that
$$\sum_{n \leq x} \frac{f(n)}{n} = A x + B \log x + C \psi(x) + D + R(x)$$
and $R(x) \ll x^{-a} (\log x)^E$ with $a,E \geq 0$. 

   \item[4.] $f \in \mathcal{M}_4(A,\alpha,\beta)$ if there exist $A > 0$, $\alpha \geq 1$ and $\alpha > \beta \geq 0$ such that

\begin{alignat}{1}
     \sum_{n \leq  x} \frac{f(n)}{n} = Ax^{\alpha} + O \left (x^{\beta} \right). \label{h:4}
\end{alignat}

\end{itemize}
Finally, we define $0 \leq \theta_f \leq \frac{1}{2}$ and $\Delta_f  \geq 0$ such that 

\begin{alignat}{1}
     \sum_{n \leq \sqrt x} \frac{f(n)}{n} \psi \left ( \frac{x}{n} \right ) & \ll x^{\theta_f} (\log x)^{\Delta_f} \label{h:3}
\end{alignat}
and we set $\theta := \max \left ( \theta_f, \theta_{\mathrm{Id}} \right )$ and $\Delta := \max \left ( \Delta_f, \Delta_{\mathrm{Id}} \right )$.

\begin{remark}
\label{re1}
It is known \cite{hux} that one can take
$$\theta_{\mathrm{Id}}  = \frac{131}{416} \doteq 0.3149 \cdots \quad \mathrm{and} \quad \Delta_{\mathrm{Id}} = \frac{26947}{8320} \doteq 3.2388\cdots$$
\end{remark}
The following result gives further information when $f \in \mathcal{M}_3(A)$ and $f \in \mathcal{M}_4(A,\alpha,\beta)$.

\begin{lemma}
\label{le21}
Let $f \in \mathcal{M}_3(A)$. Then we have for $x$ sufficiently large
$$\sum_{n \leq x} \frac{f(n)}{n^2} = A \log x + A + G - \frac{B}{x} + \frac{C \psi(x)}{x} + O \left ( \frac{(\log x)^{E}}{x^{a+1}} + \frac{1}{x^2} \right )$$
where 
\begin{alignat}{1}
     G &:= B+C \left ( \frac{1}{2} - \gamma \right ) + D + \int_{1}^{\infty} \frac{R(t) \mathrm{d}t}{t^2}. \label{id:3} 
\end{alignat}
Let $f \in \mathcal{M}_4(A,\alpha,\beta)$. Then we have for $x$ sufficiently large

$$\sum_{n \leq x} \frac{f(n)}{n^2} = A \alpha E_{\alpha}(x) + O \left ( \mathcal{R}_{\beta}(x) \right )$$
where
\begin{alignat}{1}
   E_{\alpha}(x) := \begin{cases} \dfrac{x^{\alpha-1}}{\alpha-1}, & \mathrm{if\ } \alpha > 1; \\ & \\ \log x, & \mathrm{if\ } \alpha = 1 \end{cases} \label{p:1}
\end{alignat}
and

\begin{alignat}{1}
   \mathcal{R}_{\beta}(x) := \begin {cases} x^{\beta-1}, & \mathrm{if\ } \alpha > \beta > 1; \\ \log x, & \mathrm{if \ } \alpha > \beta = 1; \\ 1, & \mathrm{if\ } \alpha \geq 1 > \beta \geq 0. \end{cases} \label{r:1}
\end{alignat}

\end{lemma}

\begin{proof}
Let $f \in \mathcal{M}_3(A)$. Using Abel summation, we get

\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \frac{f(n)}{n^2} &= A + \frac{B \log x}{x} + \frac{C \psi(x)}{x} + \frac{D}{x} + \frac{R(x)}{x} \\
     &+ \int_{1}^{x} \frac{1}{t^2} \left ( At + B \log t + C \psi(t) + D + R(t) \right ) \mathrm{d}t \\
     &= A \log x + A + B + D + \int_{1}^{\infty} \frac{R(t) \mathrm{d}t}{t^2} - \frac{B}{x} \\
     &+ C \left ( \frac{\psi(x)}{x} + \int_{1}^{x} \frac{\psi(t) \mathrm{d}t}{t^2} \right ) + \frac{R(x)}{x} - \int_{x}^{\infty} \frac{R(t) \mathrm{d}t}{t^2}. \\
   \end{split}
\end{equation*}
The estimate
$$\int_{1}^{x} \frac{\psi(t) \mathrm{d}t}{t^2} = \frac{1}{2} - \gamma + O \left ( \frac{1}{x^2} \right)$$
which can be proven by using Euler--MacLaurin's summation formula, gives
$$ \sum_{n \leq x} \frac{f(n)}{n^2} = A \log x + A + G - \frac{B}{x} + \frac{C \psi(x)}{x} + O \left ( \frac{(\log x)^E}{x^{a+1}} + \frac{1}{x^2} \right ).$$
The proof for $f \in \mathcal{M}_4(A,\alpha,\beta)$ is similar and somewhat simpler, so we omit the details.
\end{proof}
Now we can state our main result.

\begin{theorem}
\label{t2}
Let $f$ be a real-valued multiplicative function with Dirichlet series $F(s)$.

\begin{itemize}

   \item[1.] If $f \in \mathcal{M}_1(\alpha)$, then we have for $x$ sufficiently large
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) = \frac{x^2 F(2)}{2 \zeta(2)} + O \left \{ x \prod_{p \leq x} \left ( 1 + \sum_{l=1}^{\infty} \frac{ \left | f \left ( p^l \right ) - f \left ( p^{l-1} \right ) \right |}{p^l} \right ) + x(\log x)^{\alpha} \right \}.$$ 

   \item[2.] If $f \in \mathcal{M}_2(\alpha)$, then we have for $x$ sufficiently large
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) = \frac{x^2 F(2)}{2 \zeta(2)} + O \left \{ x (\log x)^{\frac{2}{3} (\alpha+1)} (\log \log x)^{\frac{4}{3} (\alpha+1)} \right \}.$$ 

   \item[3.] If $f \in \mathcal{M}_3(A)$, then we have for $x$ sufficiently large
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) = \frac{Ax^2 \log x}{2 \zeta(2)} + \frac{x^2}{2 \zeta(2)} \left \{ A \left ( \gamma+\frac{1}{2} - \frac{\zeta'(2)}{\zeta(2)} \right ) + G \right \} + O \left \{ \left ( x^{1+\theta} + x^r \right ) (\log x)^{\Gamma} \right \}$$
where $\theta$ is given in {\rm (\ref{h:3})}, $G$ is given in {\rm (\ref{id:3})} and
$$\Gamma :=\max(2, \Delta, E+1) \quad and \quad r := \begin{cases} \frac{1}{2}(3-a), & \mathrm{if\ } 0 \leq a<1;  \\ 0, & \mathrm{if\ }a \geq 1. \end{cases}$$

   \item[4.] If $f \in \mathcal{M}_4(A,\alpha,\beta)$, then we have for $x$ sufficiently large
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) = \frac{A \alpha x^2 E_{\alpha}(x)}{2 \zeta(\alpha+1)} + O \left \{ x \prod_{p \leq x} \left ( 1 + \sum_{l=1}^{\infty} \frac{ \left | f \left ( p^l \right ) - f \left ( p^{l-1} \right ) \right |}{p^l} \right ) + x^2 \mathcal{R}_{\beta}(x) \right \}$$
where $E_{\alpha}(x)$ is given in {\rm (\ref{p:1})} and $\mathcal{R}_{\beta}(x)$ is given in {\rm (\ref{r:1})}. 
\end{itemize}

\end{theorem}

\begin{proof}

Let $f$ be a real-valued multiplicative function with Dirichlet series $F(s)$.

\begin{itemize}

   \item [1.] Set $g:=f \star \mu$. Since $\varphi = \mu \star \mathrm{Id}$, we have, using Lemma~\ref{le1}
\begin{equation*}
     \begin{split}
     \sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) &= \sum_{n \leq x} \left ( g \star \mathrm{Id} \right ) (n) = \sum_{d \leq x} g(d) \sum_{k \leq x/d} k \\
     &= \frac{1}{2} \sum_{d \leq x} g(d) \left \lfloor \frac{x}{d} \right \rfloor \left ( \left \lfloor \frac{x}{d} \right \rfloor + 1 \right ) \\
     &= \frac{1}{2} \sum_{d \leq x} g(d) \left \{ \frac{x^2}{d^2} - \frac{2x}{d} \psi \left ( \frac{x}{d} \right ) - \left ( \frac{1}{4} - \psi \left ( \frac{x}{d} \right )^2 \right ) \right \} \\
    &= \frac{x^2}{2} \sum_{d \leq x} \frac{g(d)}{d^2} - x \sum_{d \leq x} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right ) + O \left ( \sum_{d \leq x} |g(d)| \right ). \\
   \end{split}
\end{equation*}
Using (\ref{h:11}) it is easily seen that the series $\sum_{d \geq 1} g(d)d^{-2}$ is absolutely convergent, and hence we have

\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) &= \frac{x^2}{2} \sum_{d=1}^{\infty} \frac{g(d)}{d^2} - x \sum_{d \leq x} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right ) + O \left ( \sum_{d \leq x} |g(d)| + x^2 \sum_{d > x} \frac{|g(d)|}{d^2} \right ) \\
     &= \frac{x^2 F(2)}{2 \zeta(2)} - x \sum_{d \leq x} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right ) + O \left ( x (\log x)^{\alpha} + x^2 \sum_{d > x} \frac{|g(d)|}{d^2} \right ). \\
   \end{split}
\end{equation*}
Now by Abel summation and (\ref{h:11}), we get
$$x^2 \sum_{d > x} \frac{|g(d)|}{d^2} = - \sum_{d \leq x} |g(d)| + 2 x^2 \int_{x}^{\infty} \frac{1}{t^3} \left ( \sum_{d \leq t} |g(d)| \right ) \mathrm{d}t \ll x (\log x)^{\alpha}$$
and the inequality $|\psi(x/d)| \leq 1/2$ gives
$$\sum_{d \leq x} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right ) \ll \sum_{d \leq x} \frac{|g(d)|}{d} \ll \prod_{p \leq x} \left ( 1 + \sum_{l=1}^{\infty} \frac{ \left | g \left ( p^l \right ) \right |}{p^l} \right ).$$

   \item[2.] The proof is the same as before except that  we are able to treat the sum $\sum_{d \leq x} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right )$ more efficiently. Using (\ref{h:21}), (\ref{h:22}), (\ref{h:225}) and (\ref{h:23}) we see that the function $d \longmapsto g(d)d^{-1}$ satisfies the conditions of Theorem 1 of \cite{pet} which gives
$$\sum_{d \leq x e^{-(\log x)^{1/6}}} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right ) \ll (\log x)^{\frac{2}{3} (\alpha+1)} (\log \log x)^{\frac{4}{3} (\alpha+1)}$$
and, using (\ref{h:21}) and partial summation, we get
$$\sum_{x e^{-(\log x)^{1/6}} < d \leq x} \frac{g(d)}{d} \psi \left ( \frac{x}{d} \right ) \ll \sum_{x e^{-(\log x)^{1/6}} < d \leq x} \frac{|g(d)|}{d} \ll (\log x)^{\alpha + 1/6}.$$
Note that $\alpha \in [0,3/2]$ implies $(\log x)^{2(\alpha+1)/3} \geq (\log x)^{\alpha+1/6}$.

   \item [3.] Set $h:= f \star \mathrm{Id}$. Using Dirichlet's hyperbola principle, we have

\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \frac{h(n)}{n} &= \sum_{n \leq x} \sum_{d \mid n} \frac{f(d)}{d} = \sum_{n \leq x} \left ( \frac{f}{\mathrm{Id}} \star \mathbf{1} \right )(n) \\
     &= \sum_{n \leq \sqrt x} \frac{f(n)}{n} \sum_{m \leq x/n} 1 + \sum_{n \leq \sqrt x} \sum_{m \leq x/n} \frac{f(m)}{m} - \left \lfloor \sqrt{x} \right \rfloor \sum_{n \leq \sqrt x} \frac{f(n)}{n} \\
     &= \sum_{n \leq \sqrt x} \frac{f(n)}{n} \left ( \frac{x}{n} - \frac{1}{2} - \psi \left ( \frac{x}{n} \right ) \right ) \\
     &+ \sum_{n \leq \sqrt x} \left \{ \frac{Ax}{n} + B \log \frac{x}{n} + C \psi \left ( \frac{x}{n} \right ) + D + O \left ( \left ( \frac{n}{x} \right )^a (\log x)^E \right ) \right \} \\
     &- \left ( \sqrt{x} - \frac{1}{2} - \psi ( \sqrt{x}) \right ) \sum_{n \leq \sqrt x} \frac{f(n)}{n} \\
     &= x \sum_{n \leq \sqrt{x}} \frac{f(n)}{n^2} - \sum_{n \leq \sqrt{x}} \frac{f(n)}{n} \psi \left ( \frac{x}{n} \right ) + Ax \sum_{n \leq \sqrt{x}} \frac{1}{n} + B \sum_{n \leq \sqrt{x}} \log \frac{x}{n} \\
     &+ C \sum_{n \leq \sqrt{x}} \psi \left ( \frac{x}{n} \right ) + D \left ( \sqrt{x} - \frac{1}{2} - \psi(\sqrt{x}) \right ) + O \left ( x^{(1-a)/2} (\log x)^E \right ) \\
     &- \left ( \sqrt{x} - \psi(\sqrt{x}) \right ) \left ( A \sqrt{x} + \frac{B}{2} \log x + C \psi(\sqrt{x}) + D + O \left ( x^{-a/2} (\log x)^E \right ) \right ) \\
     &= x \sum_{n \leq \sqrt{x}} \frac{f(n)}{n^2} + Ax \left ( \frac{\log x}{2} + \gamma - \frac{\psi(\sqrt{x})}{\sqrt{x}} + O \left ( x^{-1} \right ) \right ) \\
     &+ B \left ( \frac{\sqrt{x} \log x}{2} + \sqrt{x} + O \left ( \log x \right ) \right ) - \frac{D}{2} - Ax - \frac{B \sqrt{x} \log x}{2} \\
     &+ \left ( A - C \right ) \sqrt{x} \psi(\sqrt{x}) + \frac{B}{2} \psi(\sqrt{x}) \log x + C \psi(\sqrt{x})^2 \\
     &+ O \left ( x^{\theta} (\log x)^{\Delta} +x^{(1-a)/2} (\log x)^E \right ) \\
     &= x \sum_{n \leq \sqrt{x}} \frac{f(n)}{n^2} + \frac{Ax \log x}{2} + Ax \left ( \gamma - 1 \right ) + B \sqrt{x} - C \sqrt{x} \psi(\sqrt{x}) \\
     &+ O \left ( x^{\theta} (\log x)^{\Delta} +x^{(1-a)/2} (\log x)^E + \log x \right ). \\
   \end{split}
\end{equation*}

\noindent
Now by Lemma~\ref{le21} we get

\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \frac{h(n)}{n} &= x \left \{ \frac{A \log x}{2} + A + G - \frac{B}{\sqrt{x}} + \frac{C \psi(\sqrt{x})}{\sqrt{x}} + O \left ( \frac{(\log x)^E}{x^{(a+1)/2}} + \frac{1}{x} \right ) \right \} \\
     &+ \frac{Ax \log x}{2} + Ax \left ( \gamma -1 \right ) + B \sqrt{x} - C \sqrt{x} \psi(\sqrt{x}) \\
     &+ O \left ( x^{\theta} (\log x)^{\Delta} +x^{(1-a)/2} (\log x)^E + \log x \right ) \\
     &= A x \log x + \left ( A \gamma + G \right ) x + O \left ( x^{\theta} (\log x)^{\Delta} +x^{(1-a)/2} (\log x)^E + \log x \right ). \\
   \end{split}
\end{equation*}
An Abel summation then gives
$$\sum_{n \leq x} h(n) = \frac{A x^2 \log x}{2} + \frac{x^2}{4} \left ( A (2 \gamma +1) + 2G \right ) + O \left ( x^{1+\theta} (\log x)^{\Delta} + x^{(3-a)/2} (\log x)^E + x \log x \right )$$
and hence

\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) &= \sum_{d \leq x} \mu(d) \sum_{k \leq x/d} h(k) \\
     &= \frac{Ax^2}{2} \sum_{d \leq x} \frac{\mu(d)}{d^2} \log \frac{x}{d} + \frac{x^2}{4} \left ( A (2 \gamma +1) + 2G \right )  \sum_{d \leq x} \frac{\mu(d)}{d^2} \\
     &+ O \left ( x^{1+\theta} (\log x)^{\Delta} + x^{(3-a)/2} (\log x)^E \sum_{d \leq x} \frac{1}{d^{(3-a)/2}} + x (\log x)^2 \right ) \\
     &= \frac{Ax^2 \log x}{2 \zeta(2)} - \frac{A \zeta'(2)}{2 \zeta(2)^2} x^2 + \frac{x^2}{4 \zeta(2)}  \left ( A (2 \gamma +1) + 2G \right ) \\
     & + O \left ( \left ( x^{1+\theta} + x^r \right ) (\log x)^{\Gamma} \right ) \\
   \end{split}
\end{equation*}
which is the asserted result. 

   \item[4.] The proof is similar to the points 1 and 2. We use $g:=f \star \mu$ and we have as above
\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \left ( \sum_{i=1}^{n} f(\gcd(i,n)) \right ) & = \sum_{d \leq x} g(d) \sum_{k \leq x/d} k \\
     &= \frac{1}{2} \sum_{d \leq x} g(d) \left \lfloor \frac{x}{d} \right \rfloor \left ( \left \lfloor \frac{x}{d} \right \rfloor + 1 \right ) \\
     &= \frac{x^2}{2} \sum_{d \leq x} \frac{g(d)}{d^2} +O \left ( x \sum_{d \leq x} \frac{|g(d)|}{d}  \right ) \\
     &= \frac{x^2}{2} \sum_{d \leq x} \frac{\mu(d)}{d^2}\sum_{k \leq x/d} \frac{f(k)}{k^2} +O \left ( x \sum_{d \leq x} \frac{|g(d)|}{d}  \right ) \\
   \end{split}
\end{equation*}

and using Lemma~\ref{le21} gives the desired result.
\end{itemize}
The proof of Theorem~\ref{t2} is complete. 
\end{proof}

\section{Applications}
\label{t:3}
We first introduce some additional notation. The functions $\mu, \tau, \sigma, \ \varphi, \ \mathrm{Id}$ and $\mathbf{1}$ have their usual meanings and we add the following multiplicative functions.

\begin{itemize}
   \item $\beta(n)$ is the number of square-full divisors of $n$.
   \item $a(n)$ is the number of non-isomorphic abelian groups of order $n$. 
   \item $\tau^{(e)}(n)$ and $\sigma^{(e)}(n)$ are respectively the number and the sum of exponential divisors of $n$. 
   \item If $k \geq 2$ is any fixed integer, $\mu_k$ is the characteristic function of the set of $k$-free integers, $\tau_k$ is the $k$-th Piltz divisor function defined by $\tau_k = \underbrace{\mathbf{1} \star \dotsb \star \mathbf{1}}_{k \ \mathrm{times}}$ with $\tau_2=\tau$, $\tau_{(k)}(n)$ is the number of $k$-free divisors of $n$ with $\tau_{(2)}=2^{\omega}$ and $\gamma_k(n)$ is the greatest $k$-free divisor of $n$. 
   \item If $\K / \Q$ is any fixed number field of degree $d \geq 2$, $\nu_{\K}(n)$ is the number of nonzero integral ideals of norm $n$. The Dedekind zeta-function of $\K$ is denoted by $\zeta_{\K}$.
\end{itemize}
The following lemma gives the distribution of these functions into the classes $\mathcal{M}_i$ .

\begin{lemma}
\label{le31}
Let $k \geq 2$ be a fixed integer. We have the following distribution. 

\begin{center}
   \begin{tabular}{|c|c|c|c|}
   \hline
   &  & & \\
   $\mathcal{M}_1(\alpha)$ & $\mathcal{M}_2(\alpha)$ & $\mathcal{M}_3(A)$ & $\mathcal{M}_4(A,\alpha,\beta)$ \\
   &  & & \\
   \hline
   &  & & \\
   $\beta \in \mathcal{M}_1(0)$ & $\tau \in \mathcal{M}_2(0)$ & $\varphi \in \mathcal{M}_3 \left ( \zeta(2)^{-1} \right )$ & $\gamma_k \in \mathcal{M}_4\left ( A_k,1,\frac{1}{k} \right )$ \\
   & & & \\
   $\tau^{(e)} \in \mathcal{M}_1(0)$ & $\tau_{(k)} \in \mathcal{M}_2(0)$ &  $\sigma \in \mathcal{M}_3(\zeta(2))$ &  \\
   & & & \\
   $\mu_k \in \mathcal{M}_1(0)$ & $\mu \in \mathcal{M}_2(1)$ & $\sigma^{(e)} \in \mathcal{M}_3(2\kappa)$ & \\
   & & & \\   
   $a \in \mathcal{M}_1(0)$ &  &  & \\
   & & & \\   
   \hline
   \end{tabular}
\end{center}
where $\kappa \doteq 0.568$ and

\begin{alignat}{1}
   A_k:= \prod_{p} \left ( 1 - \frac{1}{p^{k-1}(p+1)} \right ). \label{id:4}
\end{alignat}

\end{lemma}

\begin{proof}

In the sequel, $P(n)$ is the number of unrestricted partitions of $n$.

\begin{itemize}

   \item[1.] For the class $\mathcal{M}_1(\alpha)$, use

\begin{equation*}
   \begin{split}
     & \left ( \beta \star \mu \right )(n) = \begin{cases} 1, & \mathrm{if\ } n \ \text{\rm{is square-full}}; \\ 0, & \mathrm{otherwise} \end{cases} \\
     & \left ( \mu_k \star \mu \right )(n) = \begin{cases} (-1)^{\omega(m)}, & \mathrm{if\ } n=m^k \ \mathrm{and\ } \mu_2(m)=1; \\ 0, & \mathrm{otherwise}
 \end{cases} \\
   \end{split}
\end{equation*}
and for the function $a$ we have $|(a \star \mu)(p) | = P(1)-1=0$ and for all integers $l \geq 2$ we have $\left | (a \star \mu) \left ( p^l \right ) \right | = \left |P(l) - P(l-1) \right | < 2 \times 5^{l/4}$ (see \cite{kra} for instance) so that the function $|a \star \mu|$ satisfies Wirsing's conditions (i.e. $0 \leq f(p^l) \leq \lambda_1 \lambda_2^l$ for some real numbers $\lambda_1 >0$ and $0 \leq \lambda_2 < 2$) and hence
$$\sum_{n \leq x} \left | (a \star \mu) (n) \right | \ll \frac{x}{\log x} \exp \left ( \sum_{p \leq x} \frac{ \left | (a \star \mu) (p) \right |}{p} \right ) \ll \frac{x}{\log x}.$$
For the function $\tau^{(e)}$ we use $(\tau^{(e)} \star \mu)(p) = \tau(1)-1=0$ and for all integer $l \geq 2$ we have $(\tau^{(e)} \star \mu) \left ( p^l \right ) = \tau(l) - \tau(l-1)$ (see \cite{wu}) so that
$$\sum_{n \leq x} \left | (\tau^{(e)} \star \mu)(n) \right | \ll \frac{x}{\log x}.$$

   \item[2.] For the class $\mathcal{M}_2(\alpha)$, we use the fact that $\tau \star \mu = \mathbf{1}$ and $\tau_{(k)} \star \mu = \mu_k$ which proves the result for $\tau$ and $\tau_{(k)}$. The function $\mu$ needs more work. First we have

$$\left ( \mu \star \mu \right )(n) = \begin{cases} (-2)^{\omega(a)}, & \mathrm{if\ } n=ab^2 \ \mathrm{with\ } (a,b)=1 \ \mathrm{and\ } \mu_2(a)=\mu_2(b)=1; \\ 0, & \mathrm{otherwise} \end{cases}$$

\noindent
so that the conditions (\ref{h:22}), (\ref{h:225}) and (\ref{h:23}) are easily checked. We now prove the following identity

\begin{alignat}{1}
   \sum_{n \leq x} \left | \left ( \mu \star \mu \right )(n) \right | = A_0 x \log x + A_1 x + O \left ( x^{1/2} (\log x)^3 \right ) \label{f:0}
\end{alignat}
where $A_0 = \prod_{p} \left ( 1 - 2p^{-2} + p^{-4} \right ) \approx 0.3695 \cdots$ and $A_1 = A_0 \left ( 2 \gamma -1 + 4 \sum_p \frac{\log p}{p^2-1} \right )$ which implies condition (\ref{h:21}). 

To do this we first set $f(n) := \left | \left ( \mu \star \mu \right )(n) \right |$ which is multiplicative with Dirichlet series $F(s) = \zeta(s)^2 H(s)$, where $H(s) := \prod_{p} \left ( 1-2p^{-2s} + p^{-4s} \right )$ is absolutely convergent in the half-plane $\sigma > 1/2$. Moreover, if we set $H(s) := \sum_{n=1}^{\infty} h(n)n^{-s}$, then we have from the Euler product

$$h(n) = \begin{cases} (-2)^{\omega(a)}, & \mathrm{if\ } n=a^2b^4 \ \mathrm{with\ } (a,b)=1 \ \mathrm{and\ } \mu_2(a)=\mu_2(b)=1; \\ 0, & \mathrm{otherwise} \end{cases}$$
so that 

$$\sum_{n \leq x} \frac{|h(n)|}{n^{1/2}} \leq \sum_{a \leq x^{1/2}} \frac{2^{\omega(a)}}{a} \sum_{b \leq (x/a^2)^{1/4}} \frac{1}{b^2} \ll (\log x)^2.$$
Now we are able to show (\ref{f:0}). From the factorization $F(s) = \zeta(s)^2 H(s)$, we infer that

\begin{equation*}
   \begin{split}
     \sum_{n \leq x} f(n) &= \sum_{n \leq x} \left ( \tau \star h \right )(n) = \sum_{d \leq x} h(d) \sum_{k \leq x/d} \tau(k) \\
     & = \sum_{d \leq x} h(d) \left \{ \frac{x}{d} \log \frac{x}{d} + \frac{x}{d} (2 \gamma - 1 ) + O \left ( \left ( \frac{x}{d} \right )^{1/2} \right ) \right \} \\
     &= x (\log x + 2 \gamma -1) \sum_{d \leq x} \frac{h(d)}{d} - x \sum_{d \leq x} \frac{h(d) \log d}{d} + O \left \{ x^{1/2} \sum_{d \leq x} \frac{|h(d)|}{d^{1/2}} \right \} \\
     &= H(1) x \log x  + x \left \{ H(1) (2 \gamma -1) + H'(1) \right \} + O \left ( x^{1/2} (\log x)^2 \right ) \\
     & + O \left ( x \log x \sum_{d > x} \frac{|h(d)|}{d} + x \sum_{d > x} \frac{|h(d)| \log d}{d} \right ) \\
   \end{split}
\end{equation*}
and we conclude the proof by using Abel summation to get

$$\sum_{d > x} \frac{|h(d)|}{d} \ll x^{-1/2} (\log x)^2 \quad \mathrm{and} \quad \sum_{d > x} \frac{|h(d)| \log d}{d} \ll x^{-1/2} (\log x)^3.$$

   \item[3.] For the class $\mathcal{M}_3(A)$, we first have the well known estimates

\begin{equation*}
   \begin{split}
     & \sum_{n \leq x} \frac{\varphi(n)}{n} = \frac{x}{\zeta(2)} + O \left ( (\log x)^{2/3} (\log \log x)^{4/3} \right ). \\
     & \sum_{n \leq x} \frac{\sigma(n)}{n} = x \zeta(2) - \frac{\log x}{2} + O \left ( (\log x)^{2/3} \right ). \\
   \end{split}
\end{equation*}
For the function $\sigma^{(e)}$ one can deduce from the results proven in \cite{pet, pet2} that 
$$\sum_{n \leq x} \frac{\sigma^{(e)}(n)}{n} = 2\kappa x + O \left ( (\log x)^{5/3} \right ).$$

   \item[4.] For the class $\mathcal{M}_4(A,\alpha,\beta)$, use (see \cite{sur})

\begin{equation*}
   \begin{split}
     & \sum_{n \leq x} \frac{\gamma_k(n)}{n} = A_k x + O \left ( x^{1/k} \right ) \\
   \end{split}
\end{equation*}
where $A_k$ is given in (\ref{id:4}).

\end{itemize}
The proof is complete.
\end{proof}
For the function $\nu_{\K}$, we have the following result in the case of Galois extensions.

\begin{lemma}
\label{le32}
Let $\K/ \Q$ be a Galois extension of degree $d \geq 2$. Then, for every positive integer $n$, we have
$$\left | (\nu_{\K} \star \mu)(n) \right | \leq \tau_{d-1} (n)$$
so that $\nu_{\K} \in  \mathcal{M}_1(d-2)$.
\end{lemma}

\begin{proof}
The result is obvious for $n=1$ and, by multiplicativity, it suffices to prove the inequality for prime powers. Let $p$ be any prime number and $l \geq 1$ be any integer. Since $\K / \Q$ is Galois, all prime ideals above $p$ have the same residual degree denoted by $f_p$ and we set $g_p$ to be the number of those prime ideals. If $f_p=1$ then $ \nu_{\K} \left ( p^m \right ) = \tau_{g_p} \left ( p^m \right )$ for all integer $m \geq 0$ so that
$$\left ( \nu_{\K} \star \mu \right ) \left ( p^l \right ) = \nu_{\K} \left ( p^l \right ) - \nu_{\K} \left (p^{l-1} \right ) =  \tau_{g_p} \left ( p^l \right ) - \tau_{g_p} \left (p^{l-1} \right ) = \left ( \tau_{g_p} \star \mu \right ) \left ( p^l \right ) = \tau_{g_p -1} \left ( p^l \right ).$$
If $f_p \geq 2$ and since $\K / \Q$ is Galois, we have 
$$\nu_{\K}  \left ( p^l \right )  = \begin{cases} \dbinom{g_p+l/f_p-1}{l/f_p}, & \mathrm{if\ } f_p \mid l; \\ & \\ 0, & \mathrm{otherwise} \end{cases}$$
so that
$$\left ( \nu_{\K} \star \mu \right ) \left ( p^l \right )  = \begin{cases} - 1, & \mathrm{if\ } l=1; \\ & \\ \dbinom{g_p+l/f_p-1}{l/f_p}, & \mathrm{if\ } l \geq 2 \ \mathrm{and\ } f_p \mid l \ \mathrm{and\ } f_p \nmid (l-1); \\ & \\ - \dbinom{g_p+(l-1)/f_p-1}{(l-1)/f_p}, & \mathrm{if\ } l \geq 2 \ \mathrm{and\ } f_p \nmid l \ \mathrm{and\ } f_p \mid (l-1); \\ & \\ 0, & \mathrm{otherwise}. \end{cases}$$
We have the trivial inequality $g_p \leq d$ and if $l, f_p \geq 2$ then $l/f_p \leq l/2 \leq l-1$ so that, using the fact that if $g \geq 1$ and $0 \leq x \leq y$ then $\binom{g+x-1}{x} \leq \binom{g+y-1}{y}$, we have in every case
$$\left | (\nu_{\K} \star \mu) \left ( p^l \right ) \right | \leq \binom{g_p+l-2}{l} \leq \binom{d+l-2}{l} = \tau_{d-1} \left ( p^l \right )$$
which concludes the proof.
\end{proof}

\begin{remark}
\label{re2}
One can also have the same inequality in some nonnormal cases. For instance, let $\K_3$ be a cubic field with negative discriminant, so that $\K_3$ is not Galois. The factorization of prime numbers into prime ideals is nevertheless well known and one can prove \cite{bar} that we have in fact the following situation.

\begin{center}
   \begin{tabular}{|c|c|c|}
   \hline
    & & \\
   Factorization of $(p)$ & $l$ & $\left ( \nu_{\K_3} \star \mu \right ) \left ( p^l \right )$ \\
   & & \\
   \hline
   & & \\
   Completely split & any & $l+1$ \\
   & & \\
   inert & $l \equiv 0 \pmod 3$ & $1$ \\
   & & \\
   inert & $l \equiv 1 \pmod 3$ & $-1$ \\
   & & \\
   inert & $l \equiv -1 \pmod 3$ & $0$ \\
   & & \\
   split & $l \equiv 0 \pmod 2$ & $1$ \\
   & & \\
   split & $l \equiv 1 \pmod 2$ & $0$ \\
   & & \\
   ramified & any & $1$ \\
   & & \\
   Completely ramified & any & $0$ \\
   & & \\
   \hline
   \end{tabular}
\end{center}
so that we also have in this case $\left | \left ( \nu_{\K_3} \star \mu \right ) \left ( p^l \right ) \right | \leq \tau \left ( p^l \right )$ and hence $\nu_{\K_3} \in \mathcal{M}_1(1)$.

\end{remark}
Now collecting all those results with Theorem~\ref{t2} we obtain the following estimates.

\begin{theorem}
\label{t3}
For $x$ sufficiently large, we have
\begin{itemize}
   \item[(i)] $$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \beta(\gcd(i,n)) \right ) = \frac{x^2 \zeta(4) \zeta(6)}{2 \zeta(12)} + O \left ( x  \right ).$$
   \item[(ii)] $$\sum_{n \leq x} \left ( \sum_{i=1}^{n} a(\gcd(i,n)) \right ) = \frac{x^2 }{2} \prod_{k=2}^{\infty} \zeta(2k) + O \left ( x  \right ).$$
   \item[(iii)] Let $k \geq 2$ be a fixed integer. Then we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \mu_k(\gcd(i,n)) \right ) = \frac{x^2}{2 \zeta(2k)} + O \left ( x  \right ).$$ 
   \item[(iv)] If $\widetilde{\tau}(l):=\tau(l)-\tau(l-1)-\tau(l-2)+\tau(l-3)$ for $l \geq 5$ then we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \tau^{(e)}(\gcd(i,n)) \right ) = \frac{x^2 \zeta(4)}{2} \prod_{p} \left ( 1 + \sum_{l=5}^{\infty} \frac{\widetilde{\tau}(l)}{p^{2l}} \right ) + O \left ( x  \right ).$$
   \item[(v)] Let $\Psi$ be the Dedekind arithmetical function. Then we have
$$\sum_{n \leq x} \Psi(n) = \frac{x^2 \zeta(2)}{2 \zeta(4)} + O \left ( x (\log x)^{2/3} (\log \log x)^{4/3} \right ).$$
   More generally, let $k \geq 2$ be a fixed integer. Then we have
$$\sum_{n \leq x}  \left ( \sum_{i=1}^{n} \tau_{(k)}(\gcd(i,n)) \right )  = \frac{x^2 \zeta(2)}{2 \zeta(2k)} + O \left ( x (\log x)^{2/3} (\log \log x)^{4/3} \right ).$$
   \item[(vi)] $$\sum_{n \leq x} \sigma(n) = \frac{x^2 \zeta(2)}{2} + O \left ( x (\log x)^{2/3} (\log \log x)^{4/3} \right ).$$ 
   \item[(vii)] Let $\mathcal{N}(n)$ be the number of primitive Dirichlet characters modulo $n$. Then we have
$$\sum_{n \leq x}\mathcal{N}(n) = \frac{x^2}{2 \zeta(2)^2} + O \left ( x (\log x)^{4/3}(\log \log x)^{8/3} \right ).$$ 
   \item[(viii)] Let $\K / \Q$ be a Galois extension of degree $d \geq 2$. Then we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K}(\gcd(i,n)) \right ) = \frac{x^2 \zeta_{\K}(2)}{2 \zeta(2)} + O \left ( x (\log x)^{d-1} \right ).$$ 
   \item[(ix)] Let $\K_3 / \Q$ be a cubic field with negative discriminant. Let $\K_6 / \Q$ be a normal closure of $\K_3$ and $L(s,\psi,\K_6 / \Q)$ be the Artin L-function associated to the character $\psi$ of a two-dimensional finite representation of $\mathrm{Gal} \left (\K_6 / \Q \right ) \simeq \mathcal{S}_3$. Then we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K_3}(\gcd(i,n)) \right ) = \frac{x^2 L(2,\psi,\K_6/\Q)}{2} + O \left ( x (\log x)^{2} \right ).$$
   \item[(x)] $$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \varphi(\gcd(i,n)) \right ) = \frac{x^2 \log x}{2 \zeta(2)^2} + \frac{x^2}{2 \zeta(2)^2} \left ( \gamma + \frac{1}{2} - \frac{\zeta'(2)}{\zeta(2)} + C_{\varphi} \right ) + O \left ( x^{3/2} (\log x)^{26947/8320} \right )$$
where $C_{\varphi} \in \R$. 
   \item[(xi)]
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \gcd(i,n) \right ) = \frac{x^2 \log x}{2 \zeta(2)} + \frac{x^2}{2 \zeta(2)} \left ( 2 \gamma - \frac{1}{2} - \frac{\zeta'(2)}{\zeta(2)} \right ) + O \left ( x^{547/416} (\log x)^{26947/8320} \right ).$$
   \item[(xii)] 
\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \left ( \sum_{i=1}^{n} \sigma^{(e)}(\gcd(i,n)) \right ) &= \frac{\kappa x^2 \log x}{\zeta(2)} +\frac{x^2}{\zeta(2)} \left \{ \kappa  \left ( \gamma+\frac{1}{2} - \frac{\zeta'(2)}{\zeta(2)} \right ) + C_{\sigma^{(e)}} \right \} \\
     & + O \left ( x^{3/2} (\log x)^{26947/8320} \right )
   \end{split}
\end{equation*}
where $\kappa \doteq 0.568$ and $C_{\sigma^{(e)}} \in \R$. 
   \item[(xiii)] $$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \sigma(\gcd(i,n)) \right ) = \frac{x^2 \log x}{2} + \frac{x^2}{2} \left ( \gamma + \frac{1}{2} - \frac{\zeta'(2)}{\zeta(2)} + C_{\sigma} \right ) + O \left ( x^{3/2} (\log x)^{26947/8320} \right )$$
where $C_{\sigma} \in \R$. 
   \item[(xiv)] Let $k \geq 2$ be a fixed integer. Then we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \gamma_k(\gcd(i,n)) \right ) = \frac{A_k x^2 \log x}{2 \zeta(2)} + O \left ( x^2 \right )$$
where $A_k$ is given in {\rm (\ref{id:4})}. 
\end{itemize}
\end{theorem}

\begin{remark}
The first estimate in (v) and estimate (vi) are slightly weaker than the result obtained by Walfisz \cite{wal} who proved that one can remove the factor $(\log \log x)^{4/3}$. This is due to the use of the Walfisz--P\'etermann's result in its whole generality which does not take account of these particular cases. For instance with (vi), we have here $\tau \star \mu = \mathbf{1}$ and Walfisz showed precisely that (see also section~\ref{t:4})
$$\sum_{n \leq x} \frac{\mathbf{1}(n)}{n} \psi \left ( \frac{x}{n} \right ) =\sum_{n \leq x} \frac{1}{n} \psi \left ( \frac{x}{n} \right ) \ll (\log x)^{2/3}.$$
Using this estimate gives Walfisz's result. More generally, it can be shown by induction that, for every integer $k \geq 1$, we have (see \cite{lan} for instance)
$$\sum_{n \leq x} \frac{\tau_k(n)}{n} \psi \left ( \frac{x}{n} \right ) \ll (\log x)^{k-1/3}.$$
Using the method of Theorem~\ref{t2} we get for $k \geq 2$

\begin{alignat}{1}
   \sum_{n \leq x} \left ( \sum_{i=1}^{n} \tau_k (\gcd(i,n)) \right ) = \frac{x^2 \zeta(2)^{k-1}}{2} + O \left ( x (\log x)^{k-4/3} \right ). \label{f:1}
\end{alignat}

\end{remark}

\begin{remark}
Estimate (xi) has first been obtained in \cite{chi} and later rediscovered in \cite{bor}.  
\end{remark}

\section{Quadratic fields}
\label{t:4}
Let $\K = \Q( \sqrt D)$ be a quadratic field of discriminant $D$ and set $d = |D|$. $\chi$ is the primitive Dirichlet character associated to $\K$ so that $\chi (\cdot) = \left ( d / \cdot \right )$ where $(a/b)$ is a Kronecker symbol. Finally let $L(s,\chi)$ be the $L$-function associated to $\chi$. It is known that for $\sigma > 1$, we have the factorization $\zeta_{\K}(s) = \zeta(s) L(s,\chi)$, and hence using estimate (viii) of Theorem~\ref{t3} we obtain
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) = \frac{x^2 L(2,\chi)}{2} + O \left ( x \log x \right ).$$
The purpose of this section is to show that the error term can be improved to

\begin{alignat}{1}
   \sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) = \frac{x^2 L(2,\chi)}{2} + O \left ( d^{1/2} x (\log x)^{2/3} \right ). \label{id:5}
\end{alignat}
The identity $\zeta_{\K}(s) = \zeta(s) L(s,\chi)$ implies that $\nu_{\K} \star \mu = \chi$ and thus it is easy to verify that $\nu_{\K}$ satisfies hypotheses (\ref{h:21}) and (\ref{h:22}) of the class $\mathcal{M}_2(\alpha)$ with $\alpha = 0$. We also have $\left | \left ( \nu_{\K} \star \mu \right ) \left ( p^l \right ) \right | = \left | \chi \left ( p^l \right ) \right | \leq 1$ of hypothesis (\ref{h:225}). In fact, the only condition which fails is that $p \longmapsto \left ( \nu_{\K} \star \mu \right ) \left ( p \right ) = \chi(p)$ is not ultimately monotone since $\chi(p) = 1, \ 0, \ -1$ depending on whether $p$ completely splits, is ramified or is inert in $\K$. The following result is a first step into the direction of (\ref{id:5}).

\begin{lemma}
\label{le41}
For every real number $x \geq 1$ sufficiently large and every real number $T$ such that $1 \leq T \leq x$, we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) = \frac{x^2 L(2,\chi)}{2} - x \sum_{n \leq T} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) + O \left ( x^2 T^{-2} d^{1/2} \log d + T \right ).$$
In particular, we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) = \frac{x^2 L(2,\chi)}{2} - x \sum_{n \leq x^{1/2}} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) + O \left ( x d^{1/2} \log d \right ).$$
\end{lemma}

\begin{proof}
Using Dirichlet's hyperbola principle, we get
\begin{equation*}
   \begin{split}
     \sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) &= \sum_{n \leq x} \left ( \chi \star \mathrm{Id} \right ) (n) \\
     & = \sum_{n \leq T} \chi(n) \sum_{k \leq x/n} k + \sum_{n \leq x/T} n \sum_{k \leq x/n} \chi(k) - \sum_{n \leq T} \chi(n) \sum_{n \leq x/T} n \\
     & = \frac{1}{2} \sum_{n \leq T} \chi(n) \left \lfloor \frac{x}{n} \right \rfloor \left ( \left \lfloor \frac{x}{n} \right \rfloor +1 \right ) + O \left \{ \sum_{n \leq x/T} n \left | \sum_{k \leq x/n} \chi(k) \right | \right \} \\   
     & + O \left \{ \left ( \sum_{n \leq x/T} n \right ) \left | \sum_{n \leq T} \chi(n) \right | \right \} \\
   \end{split}
\end{equation*}
and the use of the P\'{o}lya--Vinogradov inequality and the estimate
$$\left \lfloor \frac{x}{n} \right \rfloor \left ( \left \lfloor \frac{x}{n} \right \rfloor +1 \right ) = \frac{x^2}{n^2} - \frac{2x}{n} \psi \left ( \frac{x}{n} \right ) + O(1)$$
give
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) = \frac{x^2}{2} \sum_{n \leq T} \frac{\chi(n)}{n^2} - x \sum_{n \leq T} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) + O \left ( x^2 T^{-2} d^{1/2} \log d + T \right ).$$
We conclude the proof by noticing that
$$\sum_{n \leq T} \frac{\chi(n)}{n^2} = L(2,\chi) - \sum_{n > T} \frac{\chi(n)}{n^2}$$
and we get by Abel summation and the P\'{o}lya--Vinogradov inequality the estimate
$$\left | \sum_{n > T} \frac{\chi(n)}{n^2} \right | \leq \frac{4d^{1/2} \log d}{T^2}$$
giving the asserted result.
\end{proof}

\begin{remark}
The choice of $T=x^{1/2}$ is obviously not the best possible since $T=x^{2/3}$ provides an error-term of the form $O \left ( x^{2/3} d^{1/2} \log d \right )$, but it will be sufficient for our purpose.
\end{remark}
Using Lemma~\ref{le41}, we can see that (\ref{id:5}) follows at once from the estimate
\begin{alignat}{1}
   \sum_{n \leq x^{1/2}} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) \ll d^{1/2} (\log x)^{2/3} \label{id:6}
\end{alignat}
where $\chi$ is any primitive real Dirichlet character of modulus $d \geq 2$. For $x$ large we set $w(x) := \exp \left (c (\log x)^{2/3} \right )$ where $c > 0$ is an absolute constant. Since
$$\sum_{n \leq w(x)} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) \ll \sum_{n \leq w(x)} \frac{1}{n} \ll (\log x)^{2/3}$$ 
it is sufficient to prove

\begin{alignat}{1}
   \sum_{w(x) < n \leq x^{1/2}} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) \ll d^{1/2} (\log x)^{2/3}  \label{id:7}
\end{alignat}
so that we set $N \geq 1$ to be a large integer satisfying $w(x) < N \leq x^{1/2}$ and consider sums of the type

\begin{alignat}{1}
   S_N(\chi) := \sum_{N < n \leq N_1} \chi(n) \psi \left ( \frac{x}{n} \right ) \label{id:8}
\end{alignat}
with $N_1 \geq 1$ integer such that $N < N_1 \leq 2N$.

The proof of (\ref{id:7}) uses ideas developed by Walfisz in \cite{wal} and exploited by P\'etermann \cite{pet} and P\'etermann \& Wu \cite{pet2}. The first step to estimate (\ref{id:8}) is to use an approximation of the function $\psi$ by trigonometric polynomials as it was shown by Vaaler \cite{vaa}.

\begin{lemma}
\label{le42}
For all real number $x \geq 1$ and all integer $H \geq 1$ we have
$$\psi(x) = - \sum_{0 < |h| \leq H} \Phi \left ( \frac{h}{H+1} \right ) \frac{e(hx)}{2 \pi i h} + \mathcal{R}_H(x)$$
where $\Phi(t) := \pi t \left ( 1 - |t| \right ) \cot(\pi t) + |t|$ for $0 < |t| <1$ and
$$\left | \mathcal{R}_H(x) \right | \leq \frac{1}{2H+2} \sum_{|h| \leq H} \left( 1 - \frac{|h|}{H+1} \right) e(hx).$$
Moreover, we have $0 < \Phi(t) < 1$ for $0 < |t| <1$.
\end{lemma}
Note that
$$\sum_{|h| \leq H} \left( 1 - \frac{|h|}{H+1} \right) e(hx) = \frac{1}{H+1} \left | \sum_{h=0}^{H} e(hx) \right |^2$$
so that the sum in the error-term is a nonnegative real number. Using this useful tool by multiplying by $\chi(n)$ and summing over $(N,N_1]$ we get

$$S_N(\chi) = - \frac{1}{2 \pi i}  \sum_{0 < |h| \leq H} \Phi \left ( \frac{h}{H+1} \right ) \frac{1}{h}  \sum_{N < n \leq N_1} \chi(n) e \left ( \frac{hx}{n} \right ) + \sum_{N < n \leq N_1} \chi(n) \mathcal{R}_H \left( \frac{x}{n} \right)$$
with

\begin{equation*}
   \begin{split}
     \left | \sum_{N < n \leq N_1} \chi(n) \mathcal{R}_H \left( \frac{x}{n} \right) \right | & \leq \sum_{N < n \leq N_1} \left | \mathcal{R}_H \left( \frac{x}{n} \right) \right | \\
     & \leq \frac{1}{2H+2} \sum_{|h| \leq H} \left( 1 - \frac{|h|}{H+1} \right) \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} \right ) \\
     & = \frac{N}{2H+2} + \frac{1}{2H+2} \sum_{0<|h| \leq H} \left( 1 - \frac{|h|}{H+1} \right) \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} \right ) \\
     & \leq \frac{N}{2H+2} + \frac{1}{H+1} \sum_{1 \leq h \leq H} \left | \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} \right ) \right | \\
   \end{split}
\end{equation*}
so that 

\begin{equation*}
   \begin{split}
     S_N(\chi) &= -\frac{1}{2 \pi i}  \sum_{0 < |h| \leq H} \Phi \left ( \frac{h}{H+1} \right ) \frac{1}{h}  \sum_{N < n \leq N_1} \chi(n) e \left ( \frac{hx}{n} \right ) \\
     & + O \left \{ NH^{-1} + H^{-1} \sum_{1 \leq h \leq H} \left | \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} \right ) \right | \right \}. \\
   \end{split}
\end{equation*}
Since $\chi$ is primitive, we can expand it as a linear combination of additive characters using Gauss sums, which gives 

\begin{equation*}
   \begin{split}
     S_N(\chi) &= -\frac{1}{2 \pi i \tau(\overline{\chi})} \sum_{a \bmod d} \overline{\chi}(a) \sum_{0 < |h| \leq H} \Phi \left ( \frac{h}{H+1} \right ) \frac{1}{h}  \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} + \frac{an}{d} \right ) \\
     & + O \left \{ NH^{-1} + H^{-1} \sum_{1 \leq h \leq H} \left | \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} \right ) \right | \right \} \\
   \end{split}
\end{equation*}
where $\tau(\overline{\chi})$ is the Gauss sum associated to $\overline{\chi}$. Since $\chi$ is primitive, we have $|\tau(\overline{\chi})| = d^{1/2}$ so that
$$S_N(\chi) \ll NH^{-1} + d^{-1/2} \sum_{a \bmod d} \sum_{1 \leq h \leq H} \frac{1}{h}  \left | \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} + \frac{an}{d} \right ) \right | + H^{-1} \sum_{1 \leq h \leq H} \left | \sum_{N < n \leq N_1} e \left ( \frac{hx}{n} \right ) \right |.$$
The second step is given by the following lemma which lies at the heart of Walfisz's method.

\begin{lemma}
\label{le43}
Suppose that $e^{200} \leq N < N_1 \leq 2N$ and $T \geq N^2$ and let $\alpha \in \R$. Then there exists $c_0 > 0$ such that uniformly in $\alpha$ we have
$$\sum_{N < n \leq N_1} e \left ( \frac{T}{n} + \alpha n \right ) \ll N \exp \left \{ - c_0 \frac{(\log N)^3}{(\log TN^{-1})^2} \right \}.$$
\end{lemma}

\begin{proof}
Set $G_\alpha (y):=T/y + \alpha y$ for $N \leq y \leq 2N$. The case $\alpha=0$ is Lemma 2.5 of \cite{pet2}. The proof of this result uses a general theorem obtained by Karatsuba (see \cite{kar} Theorem 1, \cite{pet} Lemma C or \cite{pet2} Lemma 2.4) which requires conditions on derivatives of orders $\geq 2$ of $G_\alpha$. Since $G_\alpha^{(j)} (y) = G_0^{(j)} (y)$ for all integer $j \geq 2$, we can see that the linear phase $e(\alpha n)$ does not affect Karatsuba's result and thus we can closely follow the proof of Lemma 2.5 of \cite{pet2} giving the asserted estimate. It should be mentioned that the condition $T \geq N^2$ ensures that Karatsuba's theorem is used with derivatives of $G_\alpha$ having orders $\geq 2$.
\end{proof}
Applying Lemma~\ref{le43} we obtain with $e^{200} \leq N < N_1 \leq 2N$ and $N \leq x^{1/2}$
$$S_N(\chi) \ll NH^{-1} + N d^{1/2}\exp \left \{ - c_0 \frac{(\log N)^3}{(\log HxN^{-1})^2} \right \} \log H$$
and choosing $H = \left [\exp \left \{ (\log N)^3 / (\log x)^2 \right \} \right ]$ gives for $e^{c(\log x)^{2/3}} \leq N \leq x^{1/2}$
$$S_N(\chi) \ll \frac{N d^{1/2} (\log N)^3}{(\log x)^2} \exp \left \{ -c_1 (\log N)^3 / (\log x)^2 \right \}$$
with some absolute constants $c,c_1 > 0$ depending only on $c_0$ and where we have used the bounds $N \geq e^{c(\log x)^{2/3}}$ and $H \leq x^{1/8}$. An application of Abel summation yields
$$\sum_{N < n \leq N_1} \frac{\chi(n)}{n} \psi \left ( \frac{x}{n} \right ) \ll \frac{d^{1/2} (\log N)^3}{(\log x)^2} \exp \left \{ -c_1 (\log N)^3 / (\log x)^2 \right \}$$
for $e^{c(\log x)^{2/3}} \leq N \leq x^{1/2}$ and a similar argument to that used in the proof of Lemma 2.3 of \cite{pet2} finally gives
$$\sum_{w(x) < n \leq x^{1/2}} \frac{\chi(n)}{n} \psi \left (\frac{x}{n} \right ) \ll d^{1/2} (\log x)^{2/3}$$
which completes the proof of (\ref{id:7}) and (\ref{id:6}). The following result has thus been proved.

\begin{theorem}
\label{t4}
Let $\K / \Q$ be a quadratic field of discriminant $D$ and let $\chi$ be the quadratic Dirichlet character associated to $\K$. For every real number $x \geq \exp \left ( (\log |D|)^{3/2} \right )$ sufficiently large, we have
$$\sum_{n \leq x} \left ( \sum_{i=1}^{n} \nu_{\K} (\gcd(i,n)) \right ) = \frac{x^2 L(2,\chi)}{2} + O \left ( |D|^{1/2} x (\log x)^{2/3} \right ).$$
\end{theorem}

\section{Acknowledgments}
 I express my gratitude to the referee for his careful reading of the manuscript and the many valuable suggestions and corrections he made.

\begin{thebibliography}{9}
   \bibitem{bar} P. Barrucand, J. Loxton, and H. C. Williams, Some explicit upper bounds on the class number and regulator of a cubic field with negative discriminant, {\it Pacific J. Math.} {\bf 128} (1987), 209--222.
   \bibitem{bor} O. Bordell\`es, A note on the average order of the gcd-sum function, {\it J. Integer Seq.} {\bf 10} (2007), 
   \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles/bordelles90.html}{Article 07.3.3}. 
   \bibitem{ces} E. Ces\'{a}ro, \'Etude moyenne du plus grand commun diviseur de deux nombres, {\it Ann. Mat. Pura Appl.} {\bf 13} (1885), 235--250.
   \bibitem{chi} J. Chidambaraswamy and R. Sitaramachandrarao, Asymptotic results for a class of arithmetical functions, {\it Monatsh. Math.} {\bf 99} (1985), 19--27.
   \bibitem{hux} M. N. Huxley, Exponential sums and lattice points III, {\it Proc. Lond. Math. Soc.} {\bf 87} (2003), 591--609. 
   \bibitem{kar} A. A. Karatsuba, Estimates for trigonometric sums by Vinogradov's method, and some applications, {\it Proc. Steklov Inst. Math.} {\bf 112} (1971), 251--265. 
   \bibitem{kra} E. Kr\"{a}tzel, Die maximale Ordnung der Anzahl der wesentlich verschiedenen Abelschen Gruppen $n$-ter Ordnung, {\it Quart. J. Math.} (2) {\it Oxford Ser.} {\bf 21} (1970), 273--275.
   \bibitem{lan} A. Languasco, A singular series average and Goldbach numbers in short intervals, {\it Acta Arith.} {\bf 83} (1998), 171--179.
   \bibitem{pet} Y.-F. S. P\'{e}termann, On an estimate of Walfisz and Saltykov for an error term related to the Euler function, {\it J. Th\'eor. Nombres Bordeaux} {\bf 10} (1998), 203--236.
   \bibitem{pet2} Y.-F. S. P\'{e}termann, and J. Wu, On the sum of exponential divisors of an integer, {\it Acta Math. Hungar.} {\bf 77} (1997), 159--175.
   \bibitem{pil} S. S. Pillai, On an arithmetic function, {\it J. Annamalai Univ.} {\bf 2} (1937), 243--248.
   \bibitem{sur} D. Suryanarayana and P. Subrahmanyam, The maximal $k$-free divisor of $m$ which is prime to $n$, 1, {\it Acta Math. Acad. Sci. Hung.} {\bf 30} (1977), 49--67.
   \bibitem{tot} L. T\'{o}th, A gcd-sum function over regular integers modulo $n$, {\it J. Integer Seq.} {\bf 12} (2009), 
   \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Toth/toth3.html}{Article
   09.2.5}.
   \bibitem{vaa} J. Vaaler, Some extremal functions in Fourier analysis, {\it Bull. Amer. Math. Soc.} {\bf 12} (1985), 183--216. 
   \bibitem{wal} A. Walfisz, {\it Weylsche Exponentialsummen in der neuren Zahlentheorie}, Berlin, 1963. 
   \bibitem{wu} J. Wu, Probl\`emes de diviseurs exponentiels et entiers exponentiellement sans facteur carr\'e, {\it J. Th\'eor. Nombres Bordeaux} {\bf 7} (1995), 133--141.
\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } Composition, Dirichlet convolution, mean value results.

\bigskip
\hrule
\bigskip

\noindent
(Concerned with sequence \seqnum{A018804}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 17 2009;
revised versions received June 1 2010;   June 22 2010.
Published in {\it Journal of Integer Sequences}, June 23 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}