Count Integers Not Greater Than $a$ Coprime To $b$

Question

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?

Answer 1

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

Answer 2

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$