I am trying to find an estimate for the following sum:

$$ \sum_{\substack{n \leq x \\ n \equiv k (m)}} d(n), $$

where $d(n)$ is number of divisors of $n$. I found estimates for the case when $k$ and $m$ are coprime, but nothing explicit for general case. My expectation for this sum is that this should be known, but I can't find anything. Any ideas/references?


2 Answers 2


In the context of the "divisor problem for arithmetical progressions", there is the following article by Fouvry, Iwaniec and Katz, on "The divisor function over arithmetic progressions": http://matwbn.icm.edu.pl/ksiazki/aa/aa61/aa6134.pdf. The authors use Fourier series techniques and Weil’s estimate for Kloosterman sums to obtain $$ S(x,m,k)-D(x,m)=\sum_{n\le x, n\equiv k(m)}d(n)-\frac{1}{\phi(m)}\sum_{n\le x,(n,m)=1}d(n)=O((m^{1/2}+x^{1/3})x^{\epsilon}). $$ We have the estimate $$ \phi(m)D(x,m)=\sum_{n\le x,(n,m)=1}d(n)=xP(\log x)+O(x^{1/2}m^{\epsilon}), $$ with $P(\log x)=\frac{\phi(m)^2}{m^2}(\log x+\gamma-1)+2\frac{\phi(m)}{m}\sum_{d\mid m}\frac{\mu(d)\log d}{d}$.

Werner Georg Nowak proved in $1984$ that for any given natural numbers $m$ and $k$, $$ S(x,m,k)=\alpha x(\log x+2\gamma -1)+\beta x+ O(x^{35/108+\epsilon}), $$ for constants $\alpha$ and $\beta$ depending only on $m$ and $k$.

  • 3
    $\begingroup$ Are you sure that you have stated the upper bounds correctly? Already for $m=k=1$, it is known that the sum is asymptotic to $x\log x$ as $x \to \infty$. Or are you referring to the error terms in the corresponding Dirichlet divisor problem? $\endgroup$ Nov 18, 2013 at 17:23
  • $\begingroup$ @DanielLoughran Yes, the difference, sorry. I edited my answer. $\endgroup$ Nov 18, 2013 at 19:06
  • $\begingroup$ Those authors consider the situation where $m$ and $k$ are coprime. $\endgroup$
    – Matt Young
    Nov 18, 2013 at 19:39
  • $\begingroup$ Thank you for the answer, but this is indeed, as Matt noted, the coprime case $\endgroup$
    – psarka
    Nov 19, 2013 at 6:37
  • $\begingroup$ @PauliusŠarka I don't think so. Nowak's estimates are for all natural numbers $m,k$. $\endgroup$ Nov 19, 2013 at 8:58

Werner Georg Nowak, ON A RESULT OF SMITH AND SUBBARAO CONCERNING A DIVISOR PROBLEM Canad. Math. Bull. Vol. 27 (4), 1984.

Werner considers a different problem. He investigates the number of (positive) divisors of the positive integer n which are congruent to l modulo k. I.e. d(n;l,k) = #{d : d|n & d ≡ l(k)}.

  • $\begingroup$ No, I mean W. G. Nowak, On the divisor problem in arithmetic progressions, Comment. Math. Univ. St. Pauli 33 (1984), 209–217. $\endgroup$ Nov 19, 2013 at 9:10
  • $\begingroup$ where is this paper? i couldn't find it, not even on the author's website. all the results i find from him are to do with the quantity $d(n;l,k)$ in this answer and not with $S(x,m,k)$ of your answer. maybe i'm overlooking something? :) $\endgroup$
    – tomos
    Jan 14, 2022 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.