\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 Some Remarks on a Paper of L.\,Toth } \vskip 1cm \large Jean-Marie De Koninck \\ D\'ep. de math\'ematiques \\ Universit\'e Laval \\ Qu\'ebec, PQ G1V 0A6 \\ Canada \\ \href{mailto:jmdk@mat.ulaval.ca}{\tt jmdk@mat.ulaval.ca} \\ \ \\ Imre K\'atai \\ Computer Algebra Department \\ E\"otv\"os Lor\'and University\\ P\'azm\'any P\'eter S\'et\'any I/C \\ 1117 Budapest \\ Hungary \\ \href{mailto:katai@compalg.inf.elte.hu}{\tt katai@compalg.inf.elte.hu} \\ \end{center} \vskip .2 in \begin{abstract} Consider the functions $P(n):=\sum_{k=1}^n \gcd(k,n)$ (studied by Pillai in 1933) and $\widetilde{P}(n):=n \prod_{p|n}(2-1/p)$ (studied by Toth in 2009). From their results, one can obtain asymptotic expansions for $\sum_{n\le x} P(n)/n$ and $\sum_{n\le x} \widetilde{P}(n)/n$. We consider two wide classes of functions ${\mathcal R}$ and ${\mathcal U}$ of arithmetical functions which include $P(n)/n$ and $\widetilde{P}(n)/n$ respectively. For any given $R\in {\mathcal R}$ and $U\in {\mathcal U}$, we obtain asymptotic expansions for $\sum_{n\le x} R(n)$, $\sum_{n\le x} U(n)$, $\sum_{p\le x} R(p-1)$ and $\sum_{p\le x} U(p-1)$. \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}} %\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd,amsthm} %% DEFINITIONS \def\mand{\qquad\mbox{and}\qquad} \def\scr{\scriptstyle} \def\\{\cr} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\<{\langle} \def\>{\rangle} \def\fl#1{\left\lfloor#1\right\rfloor} \def\rf#1{\left\lceil#1\right\rceil} \def\cA{{\mathcal A}} \def\cB{{\mathcal B}} \def\cC{{\mathcal C}} \def\cE{{\mathcal E}} \def\cF{{\mathcal F}} \def\cI{{\mathcal I}} \def\cL{{\mathcal L}} \def\cM{{\mathcal M}} \def\cN{{\mathcal N}} \def\cR{{\mathcal R}} \def\cS{{\mathcal S}} \def\cP{{\mathcal P}} \def\cQ{{\mathcal Q}} \def\cT{{\mathcal T}} \def\cX{{\mathcal X}} \def\cU{{\mathcal U}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\R{{\mathbb R}} \def\C{{\mathbb C}} \def\Q{{\mathbb Q}} \def\K{{\mathbb K}} \def\L{{\mathbb L}} \def\M{{\mathbb M}} \def\eps{\varepsilon} \newcommand{\comm}[1]{\marginpar{\fbox{#1}}} \def\xxx{\vskip5pt\hrule\vskip5pt} \def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt} \section{Introduction} In 1933, Pillai \cite{kn:pillai} introduced the function $$P(n):=\sum_{k=1}^n \mbox{gcd}(k,n)$$ and showed that $$P(n) = \sum_{d|n} d\varphi(n/d) \quad \mbox{ and } \sum_{d|n}P(d) = n\tau(n) = \sum_{d|n} \sigma(d) \varphi(n/d),$$ where $\varphi$ stands for the Euler function and where $\tau(n)$ and $\sigma(n)$ stand for the number of divisors of $n$ and the sum of the divisors of $n$ respectively. It is easily shown that $$P(n)=n \tau(n) \prod_{p^a\| n} \left( 1 - \frac{ a/(a+1)}p \right).$$ In 1985, Chidambaraswamy and Sitaramachandrarao \cite{kn:chi} showed that, given an arbitrary $\varepsilon>0$, \begin{equation} \label{eq:asymP} \sum_{n\le x} P(n) = e_1 x^2\log x + e_2 x^2 + O\left( x^{1+\theta+\varepsilon} \right) , \end{equation} where $\displaystyle{e_1=\frac 1{2\zeta(2)}}$ and $\displaystyle{e_2= \frac 1{2\zeta(2)} \left( 2\gamma - \frac 12 - \frac{\zeta'(2)}{\zeta(2)} \right)}$, and where $\theta$ is the constant appearing below in Lemma \ref{lem:diviseur}, $\zeta$ stands for the Riemann Zeta Function and $\gamma$ stands for Euler's constant. Using partial summation, one easily deduces from (\ref{eq:asymP}) that \begin{equation} \label{eq:asym2} \sum_{n\le x} \frac{P(n)}n = e_1 x\log x + (2e_2-e_1) x + O\left( x^{\theta+\varepsilon} \right). \end{equation} In \cite{kn:toth}, Toth introduced the function $$ \widetilde{P}(n) = n \prod_{p|n} \left( 2 - \frac 1p \right) = n\cdot 2^{\omega(n)} \prod_{p|n} \left( 1 - \frac 1{2p} \right),$$ where $\omega(n)$ stands for the number of distinct prime factors of $n$. Toth obtained an estimate for $\sum_{n\le x} \widetilde{P}(n)$, analogous to (\ref{eq:asymP}) and from which one can easily derive an asymptotic expansion for $\sum_{n\le x} \widetilde{P}(n)/n$. In this paper, we consider two wide classes of arithmetical functions ${\cal R}$ and ${\cal U}$, the first of which includes the function $P(n)/n$, and the second of which includes $\widetilde{P}(n)/n$. Given $R\in {\cal R}$, we obtain an asymptotic expansion for $\sum_{n\le x} R(n)$; similarly for $U\in {\cal U}$. We then examine the behavior of $\sum_{p\le x} R(p-1)$ and $\sum_{p\le x} U(p-1)$. More precisely, the class ${\cal R}$ is made of the following functions $R$. First, let $\gamma(n)$ stand for the kernel of $n\ge 2$, that is $\gamma(n)=\prod_{p|n}p$ (with $\gamma(1)=1$). Then, given an arbitrary positive constant $c$, an arbitrary real number $\alpha>0$ and a multiplicative function $\kappa(n)$ satisfying $\displaystyle{|\kappa(n)|\le \frac c{\gamma(n)^\alpha}}$ for all $n\ge 2$, let $R\in {\cal R}$ be defined by \begin{equation} \label{eq:defR} R(n)= R_{\kappa,c,\alpha}(n) :=\tau(n) \sum_{d\|n} \kappa(d) = \tau(n) \prod_{p^a\|n} (1+ \kappa(p^a)). \end{equation} Here $d\|n$ means that the sum runs over the unitary divisors of $n$, that is over all divisors $d$ of $n$ for which $(d,n/d)=1$. It is easily seen that if we let $\displaystyle{\kappa(p^a)= - \frac{a/(a+1)}p}$, then the corresponding function $R(n)$ is precisely $P(n)/n$. As for the class of functions ${\cal U}$, it is made of the functions \begin{equation} \label{eq:defU} U(n)=U_{h,c,\alpha}(n):= 2^{\omega(n)} \sum_{d|n} h(d), \end{equation} where $h$ is a multiplicative function satisfying $\displaystyle{|h(d)|\le \frac c{\gamma(d)^\alpha}}$ for each integer $d\ge 2$, where $\alpha>0$ is a given number. It is easily seen that by taking $h(p)=-\frac1{2p}$ and $h(p^a)=0$ for $a\ge 2$, we obtain the particular case $U(n)=\widetilde{P}(n)/n$. Throughout this paper, $c_1,c_2,\ldots$ denote absolute positive constants. \section{Main results} \begin{theorem} \label{th:1} Let $R$ be as in (\ref{eq:defR}). For any arbitrary $\varepsilon>0$, as $x\to \infty$, \begin{equation} \nonumber T(x):=\sum_{n\le x} R(n) = A_0x \log x + B_0 x + O\left( x^{\beta} \right), \end{equation} with $$\beta= \left\{ \begin{array}{cl} \theta+\varepsilon, & \mbox{if } \alpha \ge 1-\theta;\\ 1-\alpha +\varepsilon, & \mbox{if } \alpha < 1 - \theta; \end{array} \right.$$ where $\theta$ is the number mentioned in Lemma \ref{lem:diviseur} below and where \begin{equation} \label{eq:1.9} A_0 = \sum_{d\ge 1} \frac{\lambda(d)}d \qquad \mbox{and} \qquad B_0= \sum_{d\ge 1} \frac{\lambda(d)}d (2\gamma-1 - \log d), \end{equation} the function $\lambda$ being defined below in (\ref{eq:def-lambda1}) and (\ref{eq:def-lambda2}). \end{theorem} \bigskip \begin{theorem} \label{th:2} Let $U$ be as in (\ref{eq:defU}). As $x\to \infty$, $$S(x):= \sum_{n\le x} U(n) = t_1 x \log x + t_2 x + O\left( \frac x{\log x} \right),$$ where \begin{eqnarray*} t_1 & = & \sum_{\delta=1}^\infty \frac{h(\delta) 2^{\omega(\delta)}B_1(\delta) \eta_\delta}{\delta} \sum_{n=1 \atop \gamma(n)|\delta}^\infty \frac 1n,\\ t_2 & = & \sum_{\delta=1 \atop b \in G_\delta}^\infty \frac{h(\delta) 2^{\omega(\delta)}}{\delta b} \big(B_2(\delta)\eta_\delta-2B_1(\delta)\mu_\delta - B_1(\delta) \eta_\delta \log(\delta b) \big), \end{eqnarray*} where $B_1(\delta)$ and $B_2(\delta)$ are defined below in Lemma \ref{lem:diviseur-phi}, while $\eta_\delta$ and $\mu_\delta$ are defined respectively in (\ref{eq:def-eta}) and (\ref{eq:def-mu}). \end{theorem} \bigskip \begin{theorem} \label{th:3} Let $R$ be as in (\ref{eq:defR}). As $x\to \infty$, \begin{equation} \label{eq:th3} M(x) := \sum_{p\le x} R(p-1) = K_1 x + O \left( \frac x{\log \log x} \right), \end{equation} where $\displaystyle{K_1=\frac 12 \sum_{d=1}^\infty \frac{\kappa(d)\tau(d) c_d}d }$, where $c_d$ is itself defined in Lemma \ref{lem:1-sur-phi}. \end{theorem} \bigskip \begin{theorem} \label{th:4} Let $U$ be as in (\ref{eq:defU}). As $x\to \infty$, \begin{equation} \label{eq:th4} N(x):=\sum_{p\le x} U(p-1) = K_2 x + O \left( \frac x{\log \log x} \right), \end{equation} where $K_2$ is a positive constant which may depend on the function $\kappa$. \end{theorem} \section{Preliminary results} \begin{lemma} \label{lem:diviseur} As $x\to \infty$, \begin{equation} \label{eq:1.7} D(x):=\sum_{n\le x} \tau(n) = x \log x + (2\gamma-1) x + O(x^\theta) \qquad (x\to \infty), \end{equation} for some positive constant $\theta < 1/3$. \end{lemma} \begin{proof} A proof can be found in the book of Ivi\'c \cite{kn:ivic}, where one can also find a history of the improvements concerning the size of $\theta$. \end{proof} \bigskip \begin{lemma} \label{lem:diviseur-modulo} Given $1\le \ell x} \frac 1{n\gamma(n)^\alpha} \ll \frac 1{x^\alpha}.$$ \end{lemma} \begin{proof} Writing each number $n$ as $n=rm$, where $r$ and $m$ are the square-full and square-free parts of $n$ respectively with $(r,m)=1$, we may write \begin{eqnarray*} \sum_{n>x} \frac 1{n\gamma(n)^\alpha} & = & \sum_{rm>x \atop{ \gcd(r,m)=1 \atop r\ \mbox{\tiny square-full}}} \frac{\mu^2(m)}{r\gamma(r)^\alpha m^{1+\alpha}} = \sum_{r\ge 1 \atop r\ \mbox{\tiny square-full}} \frac 1{r\gamma(r)^\alpha} \sum_{m>x/r \atop \gcd(m,r)=1} \frac{\mu^2(m)}{m^{1+\alpha}} \\ & \ll & \sum_{r\ge 1 \atop r\ \mbox{\tiny square-full}} \frac 1{r\gamma(r)^\alpha} \frac{\varphi(r)}r \int_{x/r}^\infty \frac{dt}{t^{1+\alpha}} = \frac 1{x^{\alpha}} \sum_{r\ge 1 \atop r\ \mbox{\tiny square-full}} \frac{\varphi(r)}{r^2} \left( \frac r{\gamma(r)} \right)^\alpha \\ & = & \frac 1{x^{\alpha}} \prod_p \left( 1+ \frac{p-1}{p^2(p^{1-\alpha}-1)} \right) \ll \frac 1{x^{\alpha}}. \end{eqnarray*} \end{proof} \bigskip \begin{lemma} \label{lem:selberg} Given any fixed number $z>0$, \begin{equation} \label{eq:sel} \sum_{n\le x}z^{\omega(n)} \ll x\ \log^{z-1}x. \end{equation} \end{lemma} \begin{remark} This result is a weak form of the well known Selberg-Sathe formula $$\sum_{n\le x}z^{\omega(n)}= C(t) x \log^{t-1}x +O(x\log^{t-2}x),$$ an estimate which holds uniformly for $x\ge 2$ and $|t|\le 1$, where $C(t)$ is a constant depending only on $t$ (see Selberg \cite{kn:selberg}). Here we give a simple direct proof of (\ref{eq:sel}). \end{remark} \begin{proof} For each positive integer $k$, let $$\pi_k(x):= \#\{n\le x: \omega(n)=k\}.$$ From a classical result of Hardy and Ramanujan \cite{kn:hardy}, we know that $$\pi_k(x) \le \frac{c_1 x}{(k-1)!\log x} (\log \log x + c_2)^{k-1} \qquad (x\ge 3),$$ for all $k \ge 1$, where $c_1$ and $c_2$ are some absolute constants. Using this estimate, it follows that \begin{eqnarray*} \sum_{n\le x}z^{\omega(n)} & = & \sum_{k\ge 1} \pi_k(x) z^k < c_1z \frac x{\log x} \sum_{k\ge 1} \frac{(z(\log \log x + c_2))^{k-1}}{(k-1)!} \\ & = & c_1z \frac x{\log x} e^{z\log \log x + zc_2} \ll \frac x{\log x} e^{z\log \log x} = x \log^{z-1} x, \end{eqnarray*} as required. \end{proof} \bigskip \begin{lemma} \label{lem:pi} ({\sc Brun-Titchmarsh Theorem}) Let $\pi(y;k,\ell):=\#\{p\le y: p\equiv \ell \pmod k\}$. Given a fixed positive number $\beta<1$, then, uniformly for $k\in [1,x^\beta]$, there exists a positive constant $\xi_1$ such that $$ \pi(x;k,\ell) < \xi_1 \frac x{\varphi(k) \log(x/k)}.$$ \end{lemma} \begin{proof} For a proof, see Titchmarsh \cite{kn:titchmarsh}. \end{proof} \bigskip \begin{lemma} \label{lem:bombieri} ({\sc Bombieri-Vinogradov Theorem}). Given an arbitrary positive constant $A$, and let $B=\frac 32 A+17$. Then $$ \sum_{k\le \frac{\sqrt x}{\log^B x}} \max_{\gcd(k,\ell)=1} \max_{y\le x} \left| \pi(y;k,\ell) - \frac{\mbox{li}(x)}{\varphi(k)} \right| \ll \frac x{\log^A x}.$$ \end{lemma} \begin{proof} For a proof, see Cheng-Dong \cite{kn:pan}. \end{proof} \bigskip \begin{lemma} \label{lem:p-1} Given a fixed positive number $\beta<1$, then, uniformly for $d\in [1,x^{1-\beta}]$, there exists a positive constant $\xi_3$ such that $$ \sum_{p\le x \atop p\equiv 1 \mod d} \tau(p-1) \le \xi_3 x\frac{\tau(d)}{\varphi(d)}.$$ \end{lemma} \begin{proof} Since $\displaystyle{\tau(n)\le 2 \sum_{d|n \atop d\le \sqrt n}1 }$ and $\tau(mn)\le \tau(m)\tau(n)$ for all positive integers $m,n$, it follows that \begin{eqnarray} \label{eq:tt} \nonumber E:& = & \sum_{p\le x \atop p\equiv 1 \pmod d} \tau(p-1) \\ \nonumber & \le & \tau(d) \sum_{p\le x \atop p\equiv 1 \pmod d} \tau(\frac{p-1}d) \\ & \le & 2\tau(d) \sum_{u\le \sqrt{x/d}} \pi(x;du,1). \end{eqnarray} On the other hand, since $\displaystyle{du=\sqrt d \cdot u\sqrt d \le \sqrt d \cdot \sqrt x \le x^{\frac 12 - \frac{\beta}2} \cdot x^{\frac 12} = x^{1-\frac{\beta}2}}$, we have, in light of Lemma \ref{lem:pi}, that \begin{equation} \label{eq:ttpi} \pi(x;du,-1)\le \xi_1 \frac x{\varphi(du) \log(x/du)} \le \xi_2 \frac x{\varphi(du)\log x}, \end{equation} with $\xi_2=2\xi_1/\beta$. Using (\ref{eq:ttpi}) in (\ref{eq:tt}) and keeping in mind that $\varphi(d)\varphi(u)\le \varphi(du)$ for positive integers $d,u$, we obtain that \begin{eqnarray*} E & \le & 2\xi_2 \frac x{\log x} \tau(d) \sum_{u\le \sqrt{x/d}} \frac 1{\varphi(du)} \\ & \le & 2\xi_2 \frac x{\log x} \frac{\tau(d)}{\varphi(d)} \sum_{u\le \sqrt{x/d}} \frac 1{\varphi(u)} \\ & \le & \xi_3 x \frac{\tau(d)}{\varphi(d)}, \end{eqnarray*} for some positive constant $\xi_3$, where we used the fact that $\displaystyle{\sum_{n\le y}\frac 1{\varphi(n)} \ll \log y}$, thus completing the proof of the lemma. \end{proof} \bigskip \begin{lemma} \label{lem:tau-gamma} Given fixed numbers $A>0$ and $\kappa<\alpha$, then $$ \sum_{d \ge \log^A x} \frac{\tau(d)}{d \gamma(d)^\alpha} \ll \frac 1{\log^{A\kappa}x}. $$ \end{lemma} \begin{proof} Clearly we have \begin{eqnarray*} \sum_{d \ge \log^A x} \frac{\tau(d)}{d \gamma(d)^\alpha} & \le & \sum_{d \ge \log^A x} \frac{\tau(d)}{d \gamma(d)^\alpha} \left( \frac d{\log^A x} \right)^\kappa \\ & = & \frac 1{\log^{A\kappa}x} \sum_{d\ge \log^A x} \frac{\tau(d)}{d^{1-\kappa} \gamma(d)^\alpha} \\ & < & \frac 1{\log^{A\kappa}x} \prod_p \left( 1+ \frac 2{p^{1-\kappa} p^\alpha} + \frac 2{p^{2(1-\kappa)} p^\alpha} + \ldots \right) \\ & \ll & \frac 1{\log^{A\kappa}x}, \end{eqnarray*} since the above infinite product converges in light of the fact that $\kappa<\alpha$. \end{proof} \bigskip \begin{lemma} \label{lem:1-sur-phi} Given a fixed positive integer $D$, then $$\sum_{n\le x \atop \gcd(n,D)=1} \frac 1{\varphi(n)} = c_D \log x + O(1),$$ where $$c_D= \prod_p \left( 1+ \frac 1{p(p-1)} \right) \cdot \prod_{p|D} \left(1 + \frac p{(p-1)^2} \right)^{-1}.$$ \end{lemma} \begin{remark} Note that the result of Lemma \ref{lem:1-sur-phi} is known in a more precise form (see the book of Montgomery and Vaughan \cite[pp.\ 42--43]{kn:mon}). \end{remark} \begin{proof} We first compute the generating series of $n/\varphi(n)$. We have \begin{eqnarray*} \sum_{n=1 \atop \mbox{\tiny gcd}(n,D)=1}^\infty \frac{n/\varphi(n)}{n^s} & = & \prod_{p\not|D} \left(1 + \frac{(1-1/p)^{-1}}{p^s} + \frac{(1-1/p)^{-1}}{p^{2s}} + \ldots \right) \\ & = & \frac{ \prod_{p} \left(1 + \frac{(1-1/p)^{-1}}{p^s} + \frac{(1-1/p)^{-1}}{p^{2s}} + \ldots \right) }{ \prod_{p|D} \left(1 + \frac{(1-1/p)^{-1}}{p^s} + \frac{(1-1/p)^{-1}}{p^{2s}} + \ldots \right)} \\ & = & \zeta(s) \prod_p \left(1- \frac 1{p^s} \right) \frac{ \prod_{p} \left(1 + \frac{(1-1/p)^{-1}}{p^s} + \frac{(1-1/p)^{-1}}{p^{2s}} + \ldots \right) }{ \prod_{p|D} \left(1 + \frac{(1-1/p)^{-1}}{p^s} + \frac{(1-1/p)^{-1}}{p^{2s}} + \ldots \right)} \\ & = & \zeta(s) \prod_p \left(1+ \frac 1{p^s(p-1)} \right) \prod_{p|D} \left( 1+ \frac p{(p-1)(p^s-1)} \right)^{-1}, \end{eqnarray*} which by Wintner's Theorem yields \begin{equation} \sum_{n \le x \atop \gcd(n,D)=1} \frac n{\varphi(n)} = c_D x + O(x^{1/2} \log x), \end{equation} where $$c_D = \prod_p \left( 1+ \frac 1{p(p-1)} \right) \cdot \prod_{p|D} \left(1 + \frac p{(p-1)^2} \right)^{-1}.$$ Then, using partial summation, we get that $$\sum_{n \le x \atop \gcd(n,D)=1} \frac 1{\varphi(n)} = c_D + O\left(\frac{\log x}{x^{1/2}}\right) + \int_1^x c_D \frac{dt}t + O(1)= c_D \log x + O(1),$$ as required. \end{proof} \bigskip \begin{lemma} \label{lem:noyau} For each integer $\delta\ge 2$, let $G_\delta$ be the semigroup generated by the prime factors of $\delta$, i.e. for $\delta=q_1^{\alpha_1} \ldots q_r^{\alpha_r}$, let $G_\delta=\{ q_1^{\beta_1} \ldots q_r^{\beta_r}: \beta_i \ge 0\}$. Then $$\sum_{n\in G_\delta} \frac 1n = \sum_{n=1 \atop \gamma(n)|\delta}^\infty \frac 1n \ll \log \log \delta.$$ \end{lemma} \begin{proof} Using the well known result of Landau $$\limsup_{n\to \infty} \frac n{\varphi(n) \log \log n} =e^\gamma,$$ we certainly have that there exists some constant $C>0$ such that $$\frac n{\varphi(n)} < C \log \log n \qquad (n\ge 3),$$ from which is follows easily that \begin{eqnarray*} \sum_{n=1 \atop \gamma(n)|\delta}^\infty \frac 1n & = & \prod_{p|\delta} \left( 1+ \frac 1p + \frac 1{p^2} + \ldots \right) = \prod_{p|\delta} \left(1- \frac 1p \right)^{-1} \\ &=& \frac{\delta}{\varphi(\delta)} < C \log \log \delta, \end{eqnarray*} which proves our result. \end{proof} \bigskip \begin{lemma} \label{lem:noyau2} Let $G_\delta$ be as in Lemma \ref{lem:noyau}. Then $$\sum_{\delta=1}^\infty \frac{|h(\delta)| 2^{\omega(\delta)}}\delta \sum_{b\in G_{\delta}} \frac 1b < + \infty.$$ \end{lemma} \begin{proof} In light of Lemma \ref{lem:noyau}, the fact that $\displaystyle{|h(\delta)|\le \frac{c}{\gamma(\delta)^\alpha}}$ and since given any $\varepsilon>0$, $\log \delta < \delta^\varepsilon$ provided $\delta\ge \delta_0(\varepsilon)$, we have \begin{eqnarray*} \sum_{\delta=1}^\infty \frac{|h(\delta)| 2^{\omega(\delta)}}\delta \sum_{b\in G_{\delta}} \frac 1b & \ll & \sum_{\delta=1}^\infty \frac{|h(\delta)| 2^{\omega(\delta)} \log\log \delta}\delta \\ & \ll & \sum_{\delta=1}^\infty \frac{ 2^{\omega(\delta)} \log \log \delta}{\delta \gamma(\delta)^\alpha}\\ & \ll & \sum_{\delta=\delta_0}^\infty \frac{ 2^{\omega(\delta)} }{\delta^{1-\varepsilon} \gamma(\delta)^\alpha} \\ & < & \prod_p \left(1 + \frac{2}{p^{1-\varepsilon} p^\alpha} + \frac{2}{p^{2-2\varepsilon} p^\alpha} + \ldots \right) \\ & = & \prod_p \left( 1 + \frac{2}{p^\alpha(p^{1-\varepsilon}-1)} \right) <+\infty, \end{eqnarray*} provided $\varepsilon < \alpha$. \end{proof} \bigskip \begin{lemma} \label{lem:sum-h-delta} Let $G_\delta$ be as in Lemma \ref{lem:noyau} and let $\rho(x)$ be a real function which tends to $+\infty$ as $x\to \infty$. Given any fixed positive constant $\kappa<\alpha$, we have $$Z(x):=\sum_{\rho(x) <\delta b \le x \atop b \in G_\delta} \frac{h(\delta) 2^{\omega(\delta)} }{\delta b} \ll \frac 1{\rho(x)^\kappa}.$$ \end{lemma} \begin{proof} We have \begin{equation} \label{eq:z1z2} |Z(x)| \le \sum_{\delta b > \rho(x) \atop b\in G_\delta} \frac{|h(\delta)|\cdot 2^{\omega(\delta)}}{\delta b} = \sum_{\delta b > \rho(x) \atop \delta<\rho(x)} + \sum_{\delta b > \rho(x) \atop \delta \ge \rho(x)} = Z_1+Z_2, \end{equation} say. We first estimate $Z_2$. Recalling that $|h(\delta)|\le c/\gamma(\delta)^\alpha$, \begin{eqnarray} \label{eq:z2} \nonumber Z_2 & \le & \sum_{\delta \ge \rho(x)} \frac{|h(\delta)|\cdot 2^{\omega(\delta)}}{\delta} \prod_{p|\delta} \left( 1+ \frac 1p + \frac 1{p^2} + \ldots \right) \\ \nonumber & \le & \sum_{\delta=1}^\infty \frac{|h(\delta)|\cdot 2^{\omega(\delta)}}{\delta} \prod_{p|\delta} \frac 1{1-1/p} \cdot \left( \frac{\delta}{\rho(x)} \right)^\kappa \\ & \le & \frac c{\rho(x)^\kappa} \sum_{\delta=1}^\infty \frac {2^{\omega(\delta)}}{\delta^{1-\kappa} \gamma(\delta)^\alpha} \prod_{p|\delta} \frac 1{1-1/p}. \end{eqnarray} Define $$f(\delta):=\frac{2^{\omega(\delta)}}{\delta^{1-\kappa} \gamma(\delta)^\alpha} \prod_{p|\delta} \frac 1{1-1/p}.$$ Clearly $f$ is a multiplicative function with the following values on prime powers: $$f(q^a) = \frac 2{q^\alpha\cdot q^{a(1-\kappa)} (1-1/q)}.$$ Moreover, $f$ is such that $\sum_{\delta=1}^\infty f(\delta)$ is bounded provided $\kappa<\alpha$. Hence, taking this into account in (\ref{eq:z2}), we obtain that \begin{equation} \label{eq:z2a} Z_2 \ll \frac 1{\rho(x)^\kappa}. \end{equation} We now move on to estimate $Z_1$. We have \begin{eqnarray} \label{eq:z1} \nonumber Z_1 & \le & \sum_{\delta < \rho(x)} \frac{|h(\delta)| 2^{\omega(\delta)}}{\delta} \sum_{b> \rho(x)/\delta \atop b\in G_\delta} \frac 1b \le \sum_{\delta < \rho(x)} \frac{|h(\delta)| 2^{\omega(\delta)}}{\delta} \sum_{b\in G_\delta} \frac 1b \left( \frac{b\delta}{\rho(x)} \right)^\kappa \\ & = & \frac 1{\rho(x)^\kappa} \sum_{\delta < \rho(x)} \frac{|h(\delta)| 2^{\omega(\delta)}}{\delta^{1-\kappa}} \sum_{b\in G_\delta} b^{\kappa-1}. \end{eqnarray} Since $$\sum_{b\in G_\delta} b^{\kappa-1} \le \prod_{p|\delta} \left(1+ \frac 1{p^{1-\kappa}} + \frac 1{p^{2(1-\kappa})} + \ldots \right)= \prod_{p|\delta} \left( 1- \frac 1{p^{1-\kappa}} \right)^{-1} ,$$ it follows from (\ref{eq:z1}) and the fact that $|h(\delta)| \le c/\gamma(\delta)^\alpha$, that \begin{equation} \label{eq:zia} Z_1 \le \frac c{\rho(x)^\kappa} \sum_{\delta< \rho(x)} \frac{2^{\omega(\delta)}}{\gamma(\delta)^\alpha \delta^{1-\kappa}} \prod_{p|\delta} \left( 1- \frac 1{p^{1-\kappa}} \right)^{-1} = \frac c{\rho(x)^\kappa} \sum_{\delta<\rho(x)} g(\delta), \end{equation} say, where $g$ is clearly a multiplicative function whose values at the prime powers are given by $$g(q^a) = \frac 2{q^\alpha\cdot q^{a(1-\kappa)}} \left(1 + \frac 1{q^{1-\kappa}} + \frac 1{q^{2(1-\kappa})} + \ldots\right).$$ Since we assumed that $\kappa<\alpha$and since $\displaystyle{\sum_{a=1}^\infty g(q^a) < \frac {c_3}{q^{\alpha+1-\kappa}}}$, with a suitable constant $c_3>0$, it follows that $$\sum_{\delta=1}^\infty g(\delta) = \prod_p (1+ g(p) + g(p^2) + \ldots )< +\infty.$$ Using this information, (\ref{eq:zia}) yields \begin{equation} \label{eq:z1b} Z_1 \ll \frac 1{\rho(x)^\kappa}. \end{equation} Substituting (\ref{eq:z2a}) and (\ref{eq:z1b}) in (\ref{eq:z1z2}), the lemma is proved. \end{proof} \section{Proof of Theorem~\ref{th:1}} One can easily see that $$F(s):= \sum_{n=1}^\infty \frac{R(n)}{n^s}$$ can be written as \begin{equation} \label{eq:e1} F(s) = A(s) \zeta^2(s), \end{equation} where $$ A(s) = \prod_p \left( 1+ \frac{\lambda(p)}{p^s} + \frac{\lambda(p^2)}{p^{2s}} + \ldots \right), $$ with \begin{equation} \label{eq:def-lambda1} \lambda(p) = 2 \kappa(p), \qquad \lambda(p^2) = 3 \kappa(p^2)-4 \kappa(p), \end{equation} and more generally, for each $\beta\ge 3$, by \begin{equation} \label{eq:def-lambda2} \lambda(p^\beta) = (\beta+1) \kappa(p^\beta)-2\beta \kappa(p^{\beta-1}) + (\beta-1) \kappa(p^{\beta-2}). \end{equation} Hence, $$|\lambda(p^\beta)| \le \frac{4\beta c}{p^\alpha} \qquad (\beta\ge 1).$$ Consequently, \begin{equation} \label{eq:1.6} |\lambda(d)| \le \frac{\tau(d)^{c_4}}{\gamma(d)^\alpha}, \end{equation} where $c_4$ is a suitable constant ($c_4=4c$ will do). Now observe that, in light of (\ref{eq:e1}) and of Lemma \ref{lem:diviseur}, \begin{eqnarray} \label{eq:p1} \nonumber T(x) & = & \sum_{d\le x} \lambda(d) D(x /d) \\ & = & \sum_{d\le x} \lambda(d) \left( \frac xd \log(\frac xd) + (2\gamma-1)\frac xd\right) + O \left( x^\theta \sum_{d\le x} \frac{|\lambda(d)|}{d^\theta} \right). \end{eqnarray} It follows from (\ref{eq:1.6}) and Lemma \ref{lem:1surnoyau} that \begin{equation} \label{eq:p2} \sum_{d>x} \frac{|\lambda(d)|}d \le \sum_{d>x} \frac{c \tau(d)^{c_4}}{d\gamma(d)^\alpha} \ll x^{\varepsilon-\alpha}. \end{equation} Indeed, we have $$S_U:= \sum_{d\in [U,2U]} \frac{\tau(d)^{c_4}}{d\gamma(d)} < U^\varepsilon \sum_{d\in [U,2U]} \frac 1{d\gamma(d)} = U^\varepsilon K_U,$$ say, provided $U$ is sufficiently large. Now, from Lemma \ref{lem:1surnoyau}, it follows that $K_U\le \frac c{U^\alpha}$. Hence, if we set $U_j=2^j x$ for $j=0,1,\ldots$, then, if $x$ is large enough, $$\sum_{d>x} \frac{|\lambda(d)|}d \le c \sum_{j=0}^\infty \frac{U_j^\varepsilon}{U_j^\alpha} = c\, x^{\varepsilon-\alpha} \sum_{j=0}^\infty \frac 1{2^{j(\alpha-\varepsilon)}} \ll x^{\varepsilon-\alpha}.$$ Similarly, observing that $\tau(d)^{c_4} (c+\log d) \le d^\varepsilon$ and arguing in a similar way, one can easily proves that \begin{equation}\label{eq:p3} \sum_{d>x} \frac{|\lambda(d)|\cdot |c+\log d|}d \ll x^{\varepsilon-\alpha}. \end{equation} Substituting (\ref{eq:p2}) and (\ref{eq:p3}) in (\ref{eq:p1}), one obtains \begin{equation} \label{eq:1.8} T(x)= A_0x \log x + B_0 x + O\left( x^{1-\alpha+\varepsilon} \right) + O \left( x^\theta \sum_{d\le x} \frac{|\lambda(d)|}{d^\theta} \right), \end{equation} where $\displaystyle{A_0= \sum_{d=1}^\infty \frac{\lambda(d)}d}$ and $\displaystyle{B_0=\sum_{d=1}^\infty \frac{\lambda(d)}d(2\gamma -1 -\log d)}$. Since $$\sum_{d\le x} \frac{|\lambda(d)|}{d^\theta} \le \sum_{d\le x} \frac{c\tau(d)^{c_4}}{d^\theta \gamma(d)^\alpha} \le \left\{ \begin{array}{cl} x^{\varepsilon}, & \mbox{if } \ \theta + \alpha \ge 1; \\ x^{1-(\theta+\alpha)}, & \mbox{if }\ \theta + \alpha < 1; \end{array} \right.$$ it follows that $$x^\theta \sum_{d\le x} \frac{|\lambda(d)|}{d^\theta} \le \left\{ \begin{array}{cl} x^{\theta + \varepsilon}, & \mbox{if }\ \theta + \alpha \ge 1; \\ x^{ 1 - \alpha}, & \mbox{if }\ \theta + \alpha < 1. \end{array} \right.$$ Using this last estimate in (\ref{eq:1.8}) completes the proof of Theorem~\ref{th:1}. \section{Proof of Theorem \ref{th:2}} Since $$ \sum_{n=1}^\infty \frac{2^{\omega(n)}}{n^s} = \frac{\zeta^2(s)}{\zeta(2s)} \qquad (\Re(s)>1),$$ we have that \begin{equation} \label{eq:1.12} 2^{\omega(n)} = \sum_{d^2e =n} \mu(d)\tau(e). \end{equation} Let $G_\delta$ be as in the statement of Lemma \ref{lem:noyau}. If $\delta|n$, then let $m$ be the largest divisor of $n/\delta$ which is co-prime with $\delta$, and let $b=b(\delta)\in G_\delta$ be defined implicitly by $n=\delta\cdot b \cdot m$. Note that with this setup, the numbers $m$ and $b$ are uniquely determined, and we therefore have $2^{\omega(n)} = 2^{\omega(\delta)} \cdot 2^{\omega(m)}$. Hence, \begin{eqnarray} \label{eq:1.13} \nonumber S(x) & = & \sum_{\delta \le x} h(\delta) 2^{\omega(\delta)} \sum_{b\le x/\delta \atop b\in G_\delta} \sum_{m\le \frac x{\delta b} \atop \gcd(m,\delta)=1} 2^{\omega(m)} \\ & = & \sum_{\delta \le x} h(\delta) 2^{\omega(\delta)} \sum_{b\le x/\delta \atop b\in G_\delta} E_\delta\left( \frac x{\delta b} \right), \end{eqnarray} say. We therefore need to estimate $$E_k(X):= \sum_{n\le X \atop \gcd(n,k)=1} 2^{\omega(n)}.$$ Observe that it follows from (\ref{eq:1.12}) that \begin{equation} \label{eq:1.14} E_k(X)= \sum_{d\le \sqrt X \atop \gcd(d,k)=1} \mu(d) \sum_{d^2e \le X \atop \gcd(e,k)=1} \tau(e) = \sum_{d\le \sqrt X \atop \gcd(d,k)=1} \mu(d) V_k\left( \frac X{d^2} \right), \end{equation} where $$V_k(y):= \sum_{n\le y \atop \gcd(n,k)=1} \tau(n),$$ while we trivially have \begin{equation} \label{eq:1.14a} E_k(X) \ll X \log X. \end{equation} We shall now make use of a function $\rho(x)$ satisfying \begin{equation} \label{eq:rho} \exp\left\{ \sqrt{\log x} \right\} \le \rho(x) \le \sqrt x \end{equation} and which we will later determine more precisely. \bigskip We first write (\ref{eq:1.14}) as \begin{eqnarray} \label{eq:evaS} \nonumber E_k(X) & = & \sum_{d\le \rho(X) \atop \gcd(d,k)=1} \mu(d) V_k\left( \frac X{d^2} \right) + \sum_{\rho(X) < d \le \sqrt X \atop \gcd(d,k)=1} \mu(d) V_k\left( \frac X{d^2} \right) \\ & = & W_1(X) + W_2(X), \end{eqnarray} say. It follows from Lemma \ref{lem:diviseur-phi} that \begin{eqnarray}\label{eq:evaS2} \nonumber W_2(X) & \ll & \sum_{\rho(X) < d \le \sqrt X} \frac X{d^2} \log(X/d^2) \le X \log X \sum_{d>\rho(X)} \frac 1{d^2} \\ & \ll & \frac X{\rho(X)} \log X \ll \frac X{\log X}. \end{eqnarray} On the other hand, again using Lemma \ref{lem:diviseur-phi}, we have \begin{eqnarray} \label{eq:s1temp} \nonumber W_1 (X) & = & \sum_{d\le \rho(X) \atop \gcd(d,k)=1} \mu(d) \left\{ B_1(k) \frac X{d^2} \log \left( \frac X{d^2} \right) \right. \\ \nonumber & & \qquad \left. + B_2(k) \frac X{d^2} + O \left( k^{10/3} \left( \frac X{d^2} \right)^{1/3} \log \left( \frac X{d^2} \right) \right) \right\} \\ \nonumber & = & X \log X B_1(k) \sum_{d \le \rho(X) \atop \gcd(d,k)=1} \frac{\mu(d)}{d^2} - 2 X B_1(k) \sum_{d\le \rho(X) \atop \gcd(d,k)=1} \frac{\mu(d) \log d}{d^2}\\ & & + \quad X B_2(k) \sum_{d\le \rho(X) \atop \gcd(d,k)=1} \frac{\mu(d)}{d^2} + O \left( k^{10/3} X^{1/3} \log X \right). \end{eqnarray} Since \begin{eqnarray} \label{eq:def-eta} \nonumber \sum_{d\le \rho(X) \atop \gcd(d,k)=1} \frac{\mu(d)}{d^2} & = & \sum_{d=1 \atop \gcd(d,k)=1}^\infty \frac{\mu(d)}{d^2} + O\left( \frac 1{\rho(X)} \right) = \frac 6{\pi^2} \prod_{p|k} \left(1 - \frac 1{p^2} \right)^{-1} + O\left( \frac 1{\rho(X)} \right) \\ & = & \eta_k + O\left( \frac 1{\rho(X)} \right) \end{eqnarray} say, and since \begin{equation} \label{eq:def-mu} \sum_{d\le \rho(X) \atop \gcd(d,k)=1} \frac{\mu(d) \log d}{d^2} = \sum_{d=1 \atop \gcd(d,k)=1}^\infty \frac{\mu(d) \log d}{d^2} + O\left( \frac 1{\rho(X)} \right) = \mu_k + O\left( \frac{\log X}{\rho(X)} \right), \end{equation} say, it follows that (\ref{eq:s1temp}) can be written as \begin{equation} \label{eq:evaS1} W_1(X) = X \log X B_1(k) \eta_k -2X B_1(k) \mu_k + X B_2(k) \eta_k + O\left( \frac X{\log X} \right) + O \left( k^{10/3} X^{1/3} \log X \right). \end{equation} Let us then write (\ref{eq:1.13}) as \begin{eqnarray} \label{eq:1.13a} \nonumber S(x) & = & \sum_{\delta b \le \rho(x) \atop b\in G_\delta} h(\delta) 2^{\omega(\delta)} E_\delta \left( \frac x{\delta b} \right) + \sum_{\rho(x) <\delta b \le x \atop b\in G_\delta} h(\delta) 2^{\omega(\delta)} E_\delta \left( \frac x{\delta b} \right)\\ & = & Z_1(x)+Z_2(x), \end{eqnarray} say. First of all, we have using (\ref{eq:1.14a}) and Lemma \ref{lem:sum-h-delta}, \begin{equation} \label{eq:zz2} Z_2(x) \ll \sum_{\rho(x)<\delta b \le x \atop b\in G_\delta} \frac{h(\delta) 2^{\omega(\delta)}}{\delta b} x \log(x/\delta b) \ll x \log x \frac 1{\rho(x)^\kappa} \ll \frac x{\log x}. \end{equation} On the other hand, substituting (\ref{eq:evaS2}) and (\ref{eq:evaS1}) in (\ref{eq:evaS}), we get that $Z_1(x)$ from (\ref{eq:1.13a}) can be written as \begin{eqnarray} \label{eq:Z1} \nonumber Z_1(x) & = & \sum_{\delta b \le \rho(x) \atop b \in G_\delta} h(\delta) 2^{\omega(\delta)} \left\{ \frac x{\delta b} \log \left( \frac x{\delta b} \right) B_1(\delta) \eta_\delta +(B_2(\delta)\eta_\delta-2B_1(\delta)\mu_\delta)\frac x{\delta b} \right. \\ \nonumber & & \qquad \left. + O \left( \frac{\frac x{\delta b}}{\log(\frac x{\delta b})}\right) + \left( \delta^{10/3} \left( \frac x{\delta b} \right)^{1/3} \log \left( \frac x{\delta b} \right) \right) \right\} \\ \nonumber & = & x\log x \, \sum_{\delta b \le \rho(x) \atop b \in G_\delta} \frac{h(\delta) 2^{\omega(\delta)}}{\delta b} B_1(\delta) \eta_\delta \\ \nonumber & & + x \sum_{\delta b \le \rho(x) \atop b \in G_\delta} \frac{h(\delta) 2^{\omega(\delta)}}{\delta b} \big(B_2(\delta)\eta_\delta-2B_1(\delta)\mu_\delta - B_1(\delta) \eta_\delta \log(\delta b) \big) \\ \nonumber & & \qquad + O \left( x\sum_{\delta b \le \rho(x) \atop b \in G_\delta} \frac{h(\delta) 2^{\omega(\delta)}} {\delta b\log(x/(\delta b))}\right) \\ \nonumber & & \qquad + O\left( \sum_{\delta b \le \rho(x) \atop b \in G_\delta}h(\delta) 2^{\omega(\delta)} \delta^{10/3} \left( \frac x{\delta b} \right)^{1/3} \log \left( \frac x{\delta b} \right) \right) \\ & = & (x\log x) T_1(x) + x\,T_2(x) + O(T_3(x)) + O(T_4(x)), \end{eqnarray} say. First, it follows from Lemma \ref{lem:noyau2} that \begin{equation} \label{eq:T3} T_3(x) \ll \frac x{\log x} \end{equation} and that \begin{eqnarray} \label{eq:T4} \nonumber T_4(x) & \ll & x^{1/3} \log x \sum_{\delta b\le \rho(x)} \sum_{b\in G_\delta} \frac{h(\delta) 2^{\omega(\delta)}}{\delta b} \delta^4 b^{2/3} \\ \nonumber & \ll & x^{1/3} \log x (\rho(x))^4 \sum_{\delta=1}^\infty \sum_{b\in G_\delta} \frac{h(\delta) 2^{\omega(\delta)}}{\delta b} \\ & \ll & x^{1/3} \log x (\rho(x))^4 \ll \frac x{\log x}. \end{eqnarray} On the other hand, using Lemma \ref{lem:sum-h-delta}, we have \begin{eqnarray} \label{eq:T1} \nonumber T_1(x) & = & \sum_{\delta=1 \atop b \in G_\delta}^\infty \frac{h(\delta) 2^{\omega(\delta)} B_1(\delta) \eta_\delta}{\delta b} - \sum_{\rho(x) <\delta b \le x \atop b \in G_\delta} \frac{h(\delta) 2^{\omega(\delta)} B_1(\delta) \eta_\delta}{\delta b} \\ & = & t_1 + O \left( \frac 1{\rho(x)^\kappa} \right), \end{eqnarray} say. Similarly, one can prove that \begin{equation} \label{eq:T2} T_2(x) = t_2 + O \left( \frac 1{\rho(x)^\kappa} \right), \end{equation} say. Substituting (\ref{eq:T3}), (\ref{eq:T4}), (\ref{eq:T1}) and (\ref{eq:T2}) in (\ref{eq:Z1}), we get \begin{equation} \label{eq:zz1} Z_1(x) \ll \frac{x \log x}{\rho(x)^\kappa}. \end{equation} Gathering (\ref{eq:zz2}) and (\ref{eq:zz1}) in (\ref{eq:1.13a}), we obtain $$Z(x) \ll \frac{x \log x}{\rho(x)^\kappa}.$$ Choosing $\rho(x)$, already introduced in (\ref{eq:rho}), in such a way that $$\frac{\log x}{\rho(x)^\kappa} \ll \frac 1{\log x}$$ completes the proof of Theorem~\ref{th:2}. \section{Proofs of Theorems \ref{th:3} and \ref{th:4}} Defining $$S_d(x):= \sum_{p\le x \atop{ p\equiv 1 \mod d \atop \gcd(\frac{p-1}d,d)=1}} \tau(p-1),$$ it is clear that \begin{equation} \label{eq:defM} M(x) = \sum_{d\le x-1} \kappa(d) S_d(x). \end{equation} Moreover, let $$E_d(x):= \sum_{p\le x \atop p\equiv 1 \pmod d} 2^{\omega(p-1)}\qquad \mbox{ and } \qquad H_{d,\delta} (x):= \sum_{p\le x \atop{p\equiv 1\pmod d \atop p\equiv 1 \pmod{\delta^2}}} \tau \left( \frac{p-1}{\delta^2} \right).$$ Since $$U(n) = 2^{\omega(n)} \sum_{d|n} h(d),$$ it follows that \begin{equation} \label{eq:defN} N(x) = \sum_{d\le x-1} h(d) E_d(x). \end{equation} On the other hand, since $$2^{\omega(n)} = \sum_{\delta^2 e=n} \mu(\delta) \tau(e),$$ we have $$E_d(x)= \sum_{\delta \le \sqrt {x-1}} \mu(\delta) H_{d,\delta}(x).$$ It follows from Lemma \ref{lem:p-1} that \begin{equation} \label{eq:6.8} E_d(x), S_d(x) \le c_5 \frac{\tau(d)}{\varphi(d)} x \qquad \mbox{say, for } d\le \sqrt x, \end{equation} while it is clear that \begin{equation} \label{eq:6.8dd} \nonumber \sum_{p\le x \atop p\equiv 1 \pmod d} \tau(p-1) \le \tau(d) \sum_{n\le x/d} \tau(n) \le \frac{ c_6 x \log x \cdot \tau(d)}d \qquad \mbox{for }1\le d\le x, \end{equation} and therefore, \begin{equation} \label{eq:6.9} E_d(x), S_d(x) \le c_7 \frac{\tau(d)}d x \log x. \end{equation} Let $A$ be a large constant. We shall now estimate $$T_1:= \sum_{\log^A x \le d \le x-1} |\kappa(d)|S_d(x) \qquad \mbox{and} \qquad T_2:= \sum_{\log^A x \le d \le x-1} |h(d)| E_d(x).$$ From (\ref{eq:6.8}) and (\ref{eq:6.9}), we have \begin{equation} \label{eq:t1} T_1 \ll x\log x \sum_{d\ge \sqrt x} \frac{\tau(d)}{d\gamma(d)^\alpha} + x \sum_{d\ge \log^A x}\frac{\tau(d)}{d\gamma(d)^\alpha} = x\log x\cdot U_1 + x\cdot U_2, \end{equation} say. Given a positive constant $\kappa<\alpha$, we have that \begin{eqnarray} \label{eq:u1} \nonumber U_1 & \le & \sum_{d=1}^\infty \frac{\tau(d)}{d\gamma(d)^\alpha} \left( \frac d{\sqrt x} \right)^\kappa = \frac 1{x^{\kappa/2}} \sum_{d=1}^\infty \frac{\tau(d)}{\gamma(d)^\alpha d^{1-\kappa}} \\ & \le & \frac 1{x^{\kappa/2}} \prod_p \left( 1+ \sum_{a=1}^\infty \frac{\tau(p^a)}{p^\alpha \cdot p^{a(1-\kappa)}} \right), \end{eqnarray} where this last product, which we denote by $Q$, is convergent provided $\kappa<\alpha$. In a similar way, we obtain \begin{equation} \label{eq:u2} U_2 \le \sum_{d=1}^\infty \frac{\tau(d)}{d\gamma(d)^\alpha} \left( \frac d{\log^A x} \right)^\kappa \le \frac 1{\log ^{A\kappa} x} Q. \end{equation} Substituting (\ref{eq:u1}) and (\ref{eq:u2}) in (\ref{eq:t1}), we get that \begin{equation} \label{eq:t1a} T_1 \ll \frac x{\log^{\kappa A-1} x} \qquad (0<\kappa<\alpha). \end{equation} In a similar manner, we obtain \begin{equation} \label{eq:t2a} T_2 \ll \frac x{\log^{\kappa A-1} x} \qquad (0<\kappa<\alpha). \end{equation} We further define \begin{eqnarray} \label{eq:def1} M_1(x) & = & \sum_{d\le \log^A x} \kappa(d) S_d(x), \\ N_1(x) & = & \sum_{d\le \log^A x} h(d) E_d(x). \end{eqnarray} Let us first fix $d\le \log^A x$ and move on to estimate $S_d(x)$ and $E_d(x)$, by using the Bombieri-Vinogradov Theorem. It turns out that it is more convenient to estimate $$S_d(x) - S_d(x/2) \qquad \mbox{ and } \qquad E_d(x) - E_d(x/2)$$ and similarly for $x/2$, $x/2^2$, \ldots in place of $x$. This is why, for any fixed integer $r\ge 1$, we write \begin{equation} \label{eq:M1aa} M_1(x) = \sum_{d\le \log^A x} \kappa(d) \sum_{j=0}^r A_d(x/2^j) + O\left( \frac x{2^r} \right) + O \left( \frac x{\log^{A\kappa} x} \right), \end{equation} where $$A_d(x/2^j) = S_d(x/2^j) - S_d(x/2^{j+1}).$$ Similarly, for any fixed integer $r\ge 1$, we may write \begin{equation} \label{eq:N1a} N_1(x) = \sum_{d\le \log^A x} h(d) \sum_{j=0}^r B_d(x/2^j) + O\left( \frac x{2^r} \right) + O \left( \frac x{\log^{A\kappa} x} \right), \end{equation} where $$B_d(x/2^j) = E_d(x/2^j) - E_d(x/2^{j+1}).$$ For now, fix $x$ and set \begin{equation} \label{eq:defrr} r:= \left\lfloor \frac{A\kappa \log \log x}{\log 2} \right\rfloor \quad \mbox{ so that } \quad 2^r \approx \log^{A\kappa} x. \end{equation} We now proceed to estimate $A_d(x)$ and $B_d(x)$. Clearly we have \begin{equation} \label{eq:Ad} A_d(x)= \sum_{\frac x2 < p \le x \atop {\gcd(\frac{p-1}d,d)=1 \atop p\equiv 1 \pmod d} } \tau(p-1) = \tau(d) \sum_{\frac x2 < p \le x \atop {\gcd(\frac{p-1}d,d)=1 \atop p\equiv 1 \pmod d} } \tau(\frac{p-1}d). \end{equation} Observe that $$\tau(n) = 2 \#\{(u,v): u \sqrt x/(\log^B x)$ can be bounded above, using Lemma \ref{lem:pi}, by \begin{eqnarray} \label{eq:uvd} \nonumber \tau(d) \sum_{\sqrt x/(\log^B x) < u \le \sqrt x \atop \gcd(u,d)=1} \pi(x;du,1) & \le & c_8 \tau(d) \frac{\mbox{li}(x)}{\varphi(d)} \sum_{\sqrt x/(\log^B x) < u \le \sqrt x \atop \gcd(u,d)=1} \frac 1{\varphi(u)} \\ & \le & c_9 \tau(d) \frac{\mbox{li}(x)}{\varphi(d)} B \log \log x, \end{eqnarray} where we also used Lemma \ref{lem:1-sur-phi}. Concerning the equation $\frac{p-1}d=uv$, the condition $\gcd(uv,d)=1$ is satisfied if and only if $\gcd(u,d)=1$ and $v\equiv \ell \pmod d$ for some positive integer $\ell$ co-prime to $d$, meaning that $v=\ell + dt$ and $p-1=du(\ell+dt)=du\ell +d^2 ut$ for some integer $t$. In light of these observations and of (\ref{eq:uvd}), relation (\ref{eq:uv}) can be replaced by \begin{eqnarray} \label{eq:uv2} \nonumber A_d(x) & = & \tau(d) \sum_{u \le \sqrt x/(\log^B x) \atop \gcd(u,d)=1} \sum_{\gcd(\ell,d)=1} \left( \pi(x;d^2u,1+du\ell)- \pi(\frac x2; d^2u,1+du\ell) \right) \\ & & \qquad \qquad + O \left( \frac{\tau(d)}{\varphi(d)} (\mbox{li}(x)) \log \log x \right). \end{eqnarray} We shall assume that $B$ is sufficiently large to insure that $d^2u \le \sqrt x/(\log^\Delta x)$, for some large number $\Delta$. Using Lemma \ref{lem:bombieri}, (\ref{eq:uv2}) becomes \begin{eqnarray} \label{eq:uv3} \nonumber A_d(x) & = & \tau(d) \left( \mbox{li}(x) - \mbox{li}(x/2) \right) \sum_{u \le \sqrt x/(\log^B x) \atop \gcd(u,d)=1} \sum_{\gcd(\ell,d)=1} \frac 1{\varphi(d^2u)} \\ \nonumber & & \qquad \qquad + O \left( \frac{\tau(d)}{\varphi(d)} (\mbox{li}(x))\log \log x \right). \end{eqnarray} But observe that in the above sum, we have $$ \sum_{\gcd(\ell,d)=1}\frac 1{\varphi(d^2u)} = \frac 1{\varphi(u)} \cdot \frac{\varphi(d)}{d\varphi(d)}= \frac 1{\varphi(u)}\cdot \frac 1d ,$$ so that \begin{eqnarray} \label{eq:uv4} \nonumber A_d(x) & = & \frac{\tau(d)}{d} \left( \mbox{li}(x) - \mbox{li}(x/2) \right) \sum_{u \le \sqrt x/(\log^B x) \atop \gcd(u,d)=1} \frac 1{\varphi(u)} + O \left( \frac{\tau(d)}{\varphi(d)} (\mbox{li}(x))\log \log x \right) \\ &= & \frac 14 \frac{\tau(d)c_d}{d} x + O\left( \frac{x \log \log x}{\log x} \right) , \end{eqnarray} ($c_d$ being the constant appearing in the statement of Lemma \ref{lem:1-sur-phi}) where we used Lemma \ref{lem:1-sur-phi} and the fact that $$(\mbox{li}(x) - \mbox{li}(x/2)) \cdot \left( \frac 12 \log x -B\log \log x \right) = \frac 14 x + O \left( \frac{ x \log \log x}{\log x} \right)$$ and that $$\frac{\tau(d)}{\varphi(d)}\mbox{li}(x)\log \log x =O \left( \frac{ x \log \log x}{\log x} \right).$$ Substituting (\ref{eq:uv4}) in (\ref{eq:M1aa}) and taking into account the choice of $r$ made in (\ref{eq:defrr}), we get \begin{eqnarray} \label{eq:M1zz} \nonumber M_1(x) & = & \sum_{d\le \log^A x} \kappa(d) \sum_{j=0}^r A_d(x/2^j) + O \left( \frac x{\log^{A\kappa} x} \right)\\ \nonumber & = & \frac 14 \sum_{d\le \log^A x} \frac{\kappa(d)\tau(d)c_d}{d} \sum_{j=0}^r \frac{x}{2^j} + O\left( \frac{x (\log \log x)^2}{\log x} \right) \\ & = & \frac 12 x \sum_{d\le \log^A x} \frac{\kappa(d)\tau(d)c_d}{d} + O\left( \frac{x (\log \log x)^2}{\log x} \right) \end{eqnarray} provided $A$ is chosen so that $A\kappa>1$. Finally, using Lemma \ref{lem:tau-gamma}, recalling the initial formulation of $M(x)$ given in (\ref{eq:defM}) and using (\ref{eq:M1zz}), we get $$M(x) = x \frac 12 \sum_{d=1}^\infty \frac{\kappa(d)\tau(d)c_d}{d} + O\left( \frac{x (\log \log x)^2}{\log x} \right),$$ thus completing the proof of Theorem~\ref{th:3}. We now move to complete the proof of Theorem~\ref{th:4}. For this, we shall use essentially the same kind of technique to obtain an estimate for $E_d(x)$ for $d\le \log^A x$. Since $$Q_{d,\delta}(x) := \sum_{n\le x/\delta^2} \tau(n) \le \frac{c_{10}x \log x}{\delta^2},$$ it follows that $$E_d(x) =\sum_{\delta\le \log^B x} \mu(\delta) Q_{d,\delta}(x) + O\left( \frac xd \frac 1{\log ^2 x} \right),$$ provided $B$ is sufficiently large. We shall now estimate $Q_{d,\delta}(x)$ assuming that $d\le \log^A x$ and $\delta\le \log^B x$. We proceed to estimate $$B(x)=B_{d,\delta}(x):=Q_{d,\delta}(x) - Q_{d,\delta}(x/2).$$ We have $$B(x)=2 \sum_{\frac x2 < p \le x \atop p \equiv 1 \pmod{\delta^2}} \#\{(u,v):u \sqrt x/(\log^{\Delta} x)$ for any fixed $\Delta>0$, arbitrarily large. Now let $K,L\in G_d$. Given $u,v$ such that $uv=\frac{p-1}{\delta^2}$, write $u=K \widetilde{u}$ and $v=L \widetilde{v}$, where $\gcd(\widetilde{u},d)=\gcd(\widetilde{v},d)=1$. We then have \begin{equation} \label{eq:uv1} \frac{p-1}{\delta^2} = KL \widetilde{u} \widetilde{v}. \end{equation} And in order to guarantee that $\gcd(\widetilde{v},d)=1$, we seek $\widetilde{v}$ from the arithmetical progression $\widetilde{v}=\ell + td$ with $\gcd(\ell,d)=1$. It follows from (\ref{eq:uv1}) that $$p-1= \delta^2 K L \widetilde{u} (\ell +td) = \delta^2 KL \widetilde{u} \ell + \delta^2 KL d \widetilde{u} t.$$ With this set up, we have \begin{eqnarray} \label{eq:bx} \nonumber B(x) & = & 2 \sum_{K,L\in G_d} \sum_{\gcd(\ell,d)=1} \sum_{\widetilde{u} \le (\sqrt x/K)/\log^{\Delta} x \atop \gcd(\widetilde{u},d)=1} \Big( \pi(x; \delta^2 KL d \widetilde{u}, \delta^2 KL \widetilde{u}\ell +1) \\ & & \qquad \qquad - \quad \pi(x/2; \delta^2 KL d \widetilde{u}, \delta^2 KL \widetilde{u}\ell +1) \Big) \quad + \quad O(\sqrt x). \end{eqnarray} First we drop all pairs $K,L$ for which $KL > \log^D x$, where $D$ is a fixed large number. Indeed observe that \begin{eqnarray} \label{eq:DD} \nonumber & & \sum_{\log^D x < KL \le x^{1/10} \atop K,L\in G_d} \sum_{\widetilde{u} \le \sqrt x}\quad \sum_{\ell \pmod d} \pi(x;\delta^2 KL d\widetilde{u},\delta^2 KL \widetilde{u}\ell+1) \\ \nonumber & & \qquad \qquad \qquad \qquad + \sum_{x^{1/10}\log^D x \atop K,L\in G_d} \sum_{\widetilde{u} \le \sqrt x} \frac{\varphi(d)}{\varphi(\delta^2 KL d \widetilde{u})} + \sum_{x^{1/10} < KL \le x \atop K \log^D x \atop K,L\in G_d} \frac 1{\varphi(KL)} + \frac{x\log x}{\varphi(\delta^2)} \sum_{KL > x^{1/10} \atop K,L \in G_d} \frac 1{KL} \\ & & \qquad = \frac{\mbox{li}(x)}{\varphi(\delta^2)}\cdot \log x \cdot {\cal H}_\delta(x) + \frac{x\log x}{\varphi(\delta^2)} \cdot {\cal J}_\delta(x), \end{eqnarray} say. First of all, using the fact that $\displaystyle{ \frac 1{\varphi(n)} \ll \frac{\log \log n}n}$, we have, for a fixed $\kappa>0$, \begin{eqnarray} \label{eq:ch} \nonumber {\cal H}_\delta(x) & \le & c_{11} \log\log \log x \sum_{KL > \log^D x \atop K,L \in G_d} \frac 1{KL} \le c_{11}\log \log \log x \sum_{KL > \log^D x \atop K,L \in G_d} \frac 1{KL} \left( \frac{KL}{\log^D x} \right)^\kappa \\ & \le & c_{11}\frac{\log \log \log x}{\log^{D\kappa} x} \prod_{p|d} \left( \frac 1{1- \frac 1{p^{1-\kappa}}} \right)^2. \end{eqnarray} Choosing $\kappa=1/2$ and observing that for $d< \log^A x$, we have that $\omega(d) \ll \frac{\log d}{\log \log d}$. Therefore for such a number $d$, $$\prod_{p|d} \left( \frac 1{1- \frac 1{\sqrt p}} \right)^2 < c_{12} 4^{\omega(d)} < (\log x)^{\varepsilon},$$ for any $\varepsilon>0$ arbitrarily small. Using this observation, we may conclude from (\ref{eq:ch}) that \begin{equation} \label{eq:ch2} {\cal H}_\delta(x) \le \frac{c_{13}}{(\log x)^{D/3}}, \end{equation} say. Proceeding in a somewhat similar manner, we get that \begin{eqnarray} \label{eq:cj} \nonumber {\cal J}_\delta(x) & = & \sum_{KL > x^{1/10} \atop K,L\in G_d} \frac 1{KL} \le \sum_{KL > x^{1/10} \atop K,L\in G_d} \frac 1{KL} \left( \frac{KL}{x^{1/10}} \right)^{1/2}\\ & \le & \frac 1{x^{1/20}} \prod_{p|d} \frac 1{\left(1- \frac 1{\sqrt p}\right)^2} < \frac{(\log x)^{\varepsilon}}{x^{1/20}}. \end{eqnarray} Estimates (\ref{eq:DD}), (\ref{eq:ch2}) and (\ref{eq:cj}) therefore establish that we can drop from the sum in (\ref{eq:bx}) those $K,L\in G_d$ for which $KL > \log^D x$ for a large $D$, the error thus created being no larger than $\displaystyle{O \left( \frac{ \mbox{li}(x)}{(\log x)^{D/3}}\right)}$. In light of these observations and using the fact that $\varphi(\delta^2 KL d \widetilde{u})= KL \varphi(\delta^2 d \widetilde{u})$ and that $$\sum_{K,L\in G_d \atop KL < (\log x)^D} \frac 1{KL} = \sum_{K,L\in G_d} \frac 1{KL} - \sum_{K,L\in G_d \atop KL \ge (\log x)^D} \frac 1{KL} = \prod_{p|G_d} \left( 1-\frac 1p \right)^{-2} + O \left( \frac{ \mbox{li}(x)}{(\log x)^{D/3}} \right),$$ we may write (\ref{eq:bx}) as \begin{eqnarray} \label{eq:bx2} \nonumber B(x) & = & 2(\mbox{li}(x)-\mbox{li}(x/2)) \sum_{KL<(\log x)^D \atop K,L \in G_d} \sum_{\widetilde{u} < \sqrt x/(\log x)^\Delta \atop \gcd(\widetilde{u},d)=1} \frac{\varphi(d)}{\varphi(\delta^2 KL d \widetilde{u})} + O \left( \frac{ \mbox{li}(x)}{(\log x)^{D/3}}\right) \\ & = &2(\mbox{li}(x)-\mbox{li}(x/2)) \prod_{p\in G_d} \left( 1 - \frac 1p \right)^{-2} \sum_{\widetilde{u} < \sqrt x/(\log x)^\Delta \atop \gcd(\widetilde{u},d)=1} \frac{\varphi(d)}{\varphi(\delta^2 d \widetilde{u})} + O \left( \frac{ \mbox{li}(x)}{(\log x)^{D/3}}\right). \end{eqnarray} Set $$Y_d(x):= \sum_{\widetilde{u} < \sqrt x/(\log x)^\Delta \atop \gcd(\widetilde{u},d)=1} \frac 1{\varphi(\delta^2 d \widetilde{u})}.$$ In order to evaluate $Y_d(x)$, we let $\delta= \delta_1 \delta_2$, where $\delta_1 \in G_d$, $\gcd(\delta_2,d)=1$, and $\widetilde{u} = \widetilde{u_1} \cdot \widetilde{u_2}$, where $\widetilde{u_1} \in G_{\delta_2}$, $\gcd(\widetilde{u_2}, d \delta_2)= \gcd(\widetilde{u_2}, d\delta)=1$. Then, $$\varphi(\delta^2 d \widetilde{u}) = \varphi(\delta_1^2 \delta_2^2 \widetilde{u_1}) \varphi( \widetilde{u_2}) = \varphi(\delta_1^2 d ) \varphi(\delta_2^2 \widetilde{u_1}) \varphi(\widetilde{u_2}).$$ It follows from Lemma \ref{lem:1-sur-phi} that \begin{equation} \label{eq:6.28} \sum_{\gcd(\widetilde{u_2},d\delta)=1 \atop \widetilde{u_2} \le y} \frac 1{\varphi(\widetilde{u_2})} = c_{d\delta} \log y +O(1). \end{equation} Now, the contribution of those $\widetilde{u_1}$ in $Y_d(x)$ for which $\widetilde{u_1}\in G_{\delta_2}$ and $\widetilde{u_1}> (\log x)^{\Delta_0}$ is, using (\ref{eq:6.28}), \begin{eqnarray*} && \ll \sum_{\widetilde{u_1}\in G_{\delta_2} \atop \widetilde{u_1}>(\log x)^{\Delta_0}} \frac 1{\varphi(\delta_1^2 d)} \frac 1{\varphi(\delta_2^2) \widetilde{u_1}} \sum_{ } \frac 1{\varphi(\widetilde{u_2})} \\ & & \ll (\log x) \sum \frac 1{\varphi(\delta_1^2 d)} \frac 1{\varphi(\delta_2^2) } \sum_{\widetilde{u_1}\in G_{\delta_2} \atop \widetilde{u_1}>(\log x)^{\Delta_0}} \frac 1{\widetilde{u_1}} \\ & & \ll \frac{\log x}{\varphi(\delta_1^2 d) \varphi(\delta_2^2)} \frac 1{(\log x)^{\Delta_0/2}} \sum_{\widetilde{u_1}\in G_{\delta_2}} \frac 1{\sqrt{\widetilde{u_1}}} \\ & & \ll (\log x)^{1-\Delta_0/2} \frac 1{\delta_1^2 \varphi(d) \varphi(\delta_2^2)} \prod_{p|\delta_2} \left( 1- \frac 1{\sqrt p} \right)^{-1} \\ & & \ll (\log x)^{1-\Delta_0/2} \frac 1{\varphi(d)} \frac{2^{\omega(\delta_2)}}{\delta_1^2 \delta_2^2}. \end{eqnarray*} On the other hand, the contribution of those $\widetilde{u_1} \le (\log x)^{\Delta_0}$ in $Y_d(x)$, as $\widetilde{u_2}$ runs up to $y_0:=\sqrt x/((\log x)^C \widetilde{u_1})$, and also using Lemma \ref{lem:1-sur-phi} so that \begin{equation} \label{eq:7.28} \nonumber \sum_{\gcd(\widetilde{u_2},d\delta)=1 \atop \widetilde{u_2} \le y_0} \frac 1{\varphi(\widetilde{u_2})} = \frac 12 c_{d\delta} \log x +O(\log \log x), \end{equation} we get \begin{eqnarray} \label{eq:mm} \nonumber Y_d(x) & = & \frac 12 c_{d\delta} (\log x + \log \log x) \frac 1{\varphi(\delta_1^2 d)} \frac 1{\varphi(\delta_2^2)} \sum_{\widetilde{u_1} \in G_{\delta_2}} \frac 1{\widetilde{u_1}} \\ & & \qquad + \ O \left( \frac{2^{\omega(\delta_2)}}{\delta^2 \varphi(d)} (\log x)^{1-C_0/2} \right). \end{eqnarray} Observing that $\varphi(\delta_1^2 d) = \delta_1^2 \varphi(d)$ and that $$\sum_{\widetilde{u}\in G_{\delta_2}} \frac 1{\widetilde{u}} = \prod_{p|G_{\delta_2}} \left( 1- \frac 1p \right)^{-1} = \frac{\delta_2}{\varphi(\delta_2)},$$ (\ref{eq:mm}) becomes \begin{eqnarray} \label{eq:mm1} \nonumber Y_d(x) & = & \frac 12 \frac{c_{d\delta}}{\varphi(d)} \frac 1{\delta_1^2 \delta_2^2} \frac{\delta_2}{\varphi(\delta_2)} (\log x + \log \log x) \\ & & \qquad + O \ \left( \frac{2^{\omega(\delta_2)}}{\delta^2 \varphi(d)} (\log x)^{1-C_0/2} \right). \end{eqnarray} Using (\ref{eq:mm1}) in (\ref{eq:bx2}), we obtain \begin{eqnarray*} B(x) & = & (\mbox{li}(x) - \mbox{li}(x/2)) \frac{c{_d\delta}}{\delta_1^2 \delta_2 \varphi(\delta_2)} (\log x + \log \log x) \\ & & +O \left( \frac{2^{\omega(\delta_2)}}{\delta^2 \varphi(d)} (\log x)^{1-C_0/2} \right). \end{eqnarray*} Finally, summing over $d\le (\log x)^A$ and $\delta \le (\log x)^B$, the theorem follows. \section{Final remarks} It is interesting to inquire about the solutions to the equation \begin{equation} \label{eq:f6} \widetilde{P}(n)=\widetilde{P}(n+1), \end{equation} or equivalently \begin{equation} \label{eq:f7} \frac n{\gamma(n)} \prod_{p|n} (2p-1) = \frac{n+1}{\gamma(n+1)} \prod_{q|n+1} (2q-1). \end{equation} The first 13 solutions are 45, 225, 1125, 2025, 3645, 140\,625, 164\,025, 257\,174, 703\,125, 820\,125, 1\,265\,625, 2\,657\,205 and 3\,515\,625. One can easily check that if for some positive integers $a$ and $b$, the number $p=\frac{3^a\cdot 5^b+1}2$ is a prime number, then $n=3^a\cdot 5^b$ is a solution of (\ref{eq:f6}), with $\widetilde{P}(n)=3^{a+1}\cdot 5^b$. If one could prove that there exist infinitely many primes of this form, it would follow that equation (\ref{eq:f6}) has infinitely many solutions. Interestingly, a computer search establishes that (\ref{eq:f6}) has 37 solutions $n<10^{10}$ and that 21 of them are of the form $n=3^a \cdot 5^b$. Moreover, all 37 solutions $n_0$ are such that $3^3\cdot 5|\widetilde{P}(n_0)$. To see that $3|n_0$, proceed as follows. Suppose that $3\not|\,\widetilde{P}(n_0)$, then, in light of (\ref{eq:f7}), $3\not|\,(2p-1)$ for each prime divisor $p$ of $n$ and $3\not|\,(2q-1)$ for each prime divisor $q$ of $n+1$. This would imply that $p\equiv 1 \pmod 3$ for all $p|n$ (implying that $n\equiv 1 \pmod 3$) and $q\equiv 1 \pmod 3$ for all $q|n+1$ (implying that $n+1\equiv 1 \pmod 3$), a contradiction. The fact that $3|\widetilde{P}(n_0)$ clearly implies that $5|\widetilde{P}(n_0)$. \section{Acknowledgement} The authors would like to thank the referee for some very helpful suggestions which improved the quality of this paper. \begin{thebibliography}{10} \bibitem{kn:pan} P.\,Cheng-Dong, A new mean value theorem and its applications, in {\it Recent Progress in Analytic Number Theory}, Vol. 1, (Durham, 1979), Academic Press, 1981, pp.\ 275--287. \bibitem{kn:chi} J. Chidambaraswamy and R. Sitaramachandrarao, Asymptotic results for a class of arithmetical functions, {\it Monatsh. Math.} {\bf 99} (1985), 19--27. \bibitem{kn:hardy} G. H.\,Hardy and S.\,Ramanujan, The normal number of prime factors of a number $n$, {\it Quart. J. Math.} {\bf 48} (1920), 76--92. \bibitem{kn:ivic} A.\,Ivi\'c, {\sl The Riemann Zeta Function}, John Wiley \& Sons, New York, 1985. \bibitem{kn:mon} H. L. Montgomery and R. C. Vaughan, {\sl Multiplicative Number Theory I. Classical Theory}, Cambridge University Press, 2007. \bibitem{kn:pillai} S. S.\,Pillai, On an arithmetic function, {\it J. Annamalai Univ.} {\bf 2} (1933), 243--248. \bibitem{kn:selberg} A. Selberg, Note on a paper by L. G. Sathe, {\it J. Indian Math. Soc.} {\bf 18} (1954), 83--87. \bibitem{kn:titchmarsh} E. C.\,Titchmarsh, A divisor problem, {\it Rend. Palermo} {\bf 54} (1930), 414--429 and {\bf 57} (1933), 478--479. \bibitem{kn:tolev} D. I.\,Tolev, On the divisor problem in arithmetic progressions, {\it C. R. Acad. Bulgare Sci.} {\bf 41} (1988), 33--36. \bibitem{kn:toth} L.\,Toth, A gcd-sum function over regular integers modulo $n$, {\it J. Integer Sequences} {\bf 12} (2009), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Toth/toth3.html}{Article 09.2.5}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11A25; Secondary 11N37. \noindent \emph{Keywords: } gcd-sum function, Dirichlet divisor problem, shifted primes. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 31 2009; revised version received December 29 2009. Published in {\it Journal of Integer Sequences}, December 31 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}