We know that number of coprimes less than a number can be found using euler function https://brilliant.org/wiki/eulers-totient-function/ But if there are two numbers p,q and we need to find number of numbers less than q and coprime to p. Is there any efficient method ? can we develop an algorithm.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Which is greater, $p$ or $q$? It does matter. $\endgroup$– ajotatxeCommented Apr 2, 2019 at 17:41
-
2$\begingroup$ Answered here: math.stackexchange.com/a/3158036/181098 $\endgroup$– W-t-PCommented Apr 2, 2019 at 18:02
-
2$\begingroup$ You have a very explicit formula: $\sum_{d\mid a} \mu(d) \lfloor b/d\rfloor$. Here $d$ runs over all positive divisors of $a$ (including $1$ and $a$), $\mu$ is the Mobious function, and $\lfloor b/d\rfloor$ is the largest integer not exceeding $b/d$. I am afraid I cannot explain anything beyond this. $\endgroup$– W-t-PCommented Apr 2, 2019 at 18:38
-
$\begingroup$ $\mu(1)\lfloor 10/1\rfloor+\mu(2)\lfloor 10/2\rfloor+\mu(4)\lfloor 10/4\rfloor+\mu(8)\lfloor 10/8\rfloor=1\cdot10+(-1)\cdot 5+0\cdot2+0\cdot1=5$. (The integers in $[1,10]$ co-prime with $8$ are $1,3,5,7,9$.) $\endgroup$– W-t-PCommented Apr 3, 2019 at 6:17
Add a comment
|