Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Let $\mathcal{F}_{Q;r,q}=\{\gamma=\frac{m}{n} | 0\leq m \leq n \leq Q, \gcd(m,n)=1, n \equiv r \mod q, \gcd(r,q)=1\}$. Usually, with no condition on arithmetic progression, then $\# \mathcal{F}_{Q}$ (cardinality) $=\varphi(1)+\varphi(2)+\varphi(3)+\cdots+\varphi(Q)$ $=\frac{3Q^2}{\pi^2}+O(Q\log Q)$ as $Q\rightarrow \infty$, but now how to get the cardinality for $\mathcal{F}_{Q;r,q}$ as $Q \rightarrow \infty$?

share|cite|improve this question
I suppose $\phi(\cdot)$ refers to the Euler phi (totient) function, sometimes denoted $\varphi(\cdot)$. – Srivatsan Oct 30 '11 at 3:18
Have you tried looking at a proof of the estimate for the sum of the phi-values and adapting it to the sum over an arithmetic progression? – Gerry Myerson Oct 30 '11 at 5:44
So I have tried $$\#\mathcal{F}_{Q;r,q}=\frac{1}{\varphi(q)}\sum_{n \leq Q} \varphi(Q) \sum_{\chi \mod q}\chi(n)\bar{\chi(r)}$$, which use $\varphi(n)=\sum_{d|n} \frac{\mu(d)}{d}$ becomes $$\frac{1}{\varphi(q)}\sum_{\chi \mod q} \bar{\chi(r)}\sum_{d \leq Q}\mu(d)\chi(d)\sum_{m \leq \frac{x}{d}}m \chi(m)$$, but then I don't know how to continue. – Rob Oct 31 '11 at 21:44
Are we given that $r\in(\frac{Z}{qZ})^{\times}$? If so we could use symmetry arguments. – pre-kidney Jan 23 '13 at 19:46

For all $b$ coprime to $a$, with $1 \leq b \leq a$ $$\sum_{n\leq x}_{n\equiv b \text{ mod a}}\phi(n)=(\frac{3}{\pi^2}\prod_{p\mid a}\frac{p^2}{p^2-1})x^2+O(x\ln(x)).$$ Can be shown pretty easily with out characters, though with some additional tools I think the O term could be improved.

share|cite|improve this answer

You can find a proof in the book Postnikov, A. G. Introduction to analytic number theory American Mathematical Society, 1988, (see section 4.2).

share|cite|improve this answer

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.