MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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": 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$.

share|cite|improve this answer
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? – Daniel Loughran Nov 18 '13 at 17:23
@DanielLoughran Yes, the difference, sorry. I edited my answer. – Dietrich Burde Nov 18 '13 at 19:06
Those authors consider the situation where $m$ and $k$ are coprime. – Matt Young Nov 18 '13 at 19:39
Thank you for the answer, but this is indeed, as Matt noted, the coprime case – psarka Nov 19 '13 at 6:37
@PauliusŠarka I don't think so. Nowak's estimates are for all natural numbers $m,k$. – Dietrich Burde Nov 19 '13 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)}.

share|cite|improve this answer
No, I mean W. G. Nowak, On the divisor problem in arithmetic progressions, Comment. Math. Univ. St. Pauli 33 (1984), 209–217. – Dietrich Burde Nov 19 '13 at 9:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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