Count Integers Not Greater Than $a$ Coprime To $b$ I'd like to ask how to count $f(a,b)$, the number of integers not greater than $a$ which are coprime to a given number $b$. Can $f$ be expressed using Euler's totient function?
 A: You can do this using the basic property of the Mobius function $\mu$, which is
  $$ \sum_{d\mid m} \mu(d) = \begin{cases} 1,\ m=1 \\ 0,\ m>1 \end{cases} $$
(where $m$ is a positive integer, and summation extends over all positive divisors $d$ of $m$). Namely, we have
  $$ f(a,b) = \sum_{n=1}^a \sum_{d\mid(n,b)}\mu(d) = \sum_{d\mid b} \mu(d) \sum_{\substack{1\le n\le a\\d\mid n}} 1. $$
The inner sum counts all integers $n\in[1,a]$ divisible by $d$; hence, is equal to $\lfloor a/d\rfloor$. This gives
  $$ f(a,b) = \sum_{d\mid b} \mu(d) \lfloor a/d\rfloor. $$
This is an exact formula which can be used to efficiently compute your $f(a,b)$. You can also use it to get a good approximation: since $\lfloor a/d\rfloor=a/d-\theta$, where $|\theta|<1$,
  $$ f(a,b) = a\sum_{d\mid b} \frac{\mu(d)}{d} + R = a\frac{\varphi(b)}b + R, $$
where $|R|$ does not exceed the number of divisors of $b$. 
A: In some cases yes $f$ can be expressed in terms of Eulers totient function. Any time b divides a, $f(a,b)$ is simply $\frac{a}{b}\phi(b)$. Euler totient function can also be written in terms of $f$ though. Euler totient function is $$\prod_{p|b, p\in\mathbb{P}}f(p,p)$$  in general $f(a,b)$ is $\lfloor\frac{a}{b}\rfloor\phi(b)$ plus the cardinality of the set of numbers (via inclusion-exclusion principle or f itself) not divisible by a prime factor of b less than $a\bmod b$
