3
$\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$
4
$\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$
  • $\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 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 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$ – Roddy MacPhee Mar 23 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.