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

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$$.
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$$
• So you mean $f(a,b)=\lfloor\frac{a}{b}\rfloor\phi(b)+\sum_{\substack{1\leq i \leq a\\ \forall p \ < \ a \ mod \ b \bigwedge p|b, \ p \ does \ not \ divide \ i}}1$? – Hang Wu Mar 23 at 3:16
• But I think the formula should be $f(a,b)=\lfloor\frac{a}{b}\rfloor\phi(b)+\sum_{\substack{1\leq i \leq (a \ mod \ b) \\ gcd(i,b)=1}}1$. – Hang Wu Mar 23 at 3:35
• $a=1005,b=200; f(a,b)= 5(80)+1(4)-2(1)$ because 2 and 5 are less than or equal to 5. 5 leaves 4 coprime to it, 2 takes away 2 of them. this leaves 5(80)+2= 402 numbers coprime to 200. – Roddy MacPhee Mar 23 at 12:57