6
$\begingroup$

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?

$\endgroup$

2 Answers 2

7
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – Hang Wu
    Mar 23, 2019 at 3:16
  • $\begingroup$ 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$. $\endgroup$
    – Hang Wu
    Mar 23, 2019 at 3:35
  • $\begingroup$ $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. $\endgroup$
    – user645636
    Mar 23, 2019 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .