I'm trying to find a reference for an identity I found on the Wikipedia page on the Euler totient function:
Let $n,m > 1$ be integers and let $\omega(m)$ be the prime omega function, then $$ \sum_{1 \leq j \leq n \atop \gcd(j,m) = 1} 1 \, = n \frac{\varphi(m)}{m} + O \left(2^{\omega(m)}\right). $$ The equation is cited as 'Bordellès in the external links', however the link appears to be broken and I haven't had any success searching for it elsewhere. Do any of you know where to find this identity in the literature? Thanks!
No idea of a reference, but it's easily proved: $$\sum_{\substack{j = 1 \\ (j,m) = 1}}^{n} 1 = \sum_{j = 1}^{n} \sum_{d \mid (j,m)} \mu(d) = \sum_{d \mid m} \mu(d) \sum_{\substack{j = 1 \\ j \equiv 0 \pmod{d}}}^{n} 1.$$ The sum over $j$ is equal to $\left\lfloor \frac{n}{d} \right\rfloor = \frac{n}{d} + O(1)$. So we end up with $$n \sum_{d \mid m} \frac{\mu(d)}{d} + O\left(\sum_{d \mid m} |\mu(d)|\right) = \frac{n \varphi(m)}{m} + O(2^{\omega(m)}).$$