5
$\begingroup$

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$?

  • 0
    Are we given that $r\in(\frac{Z}{qZ})^{\times}$? If so we could use symmetry arguments.2013-01-23

2 Answers 2

1

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.

1

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