Today, I found a method to counting number of coprime pairs between two sets $A$ and $B$ as follows:↵
↵
- Let $DA_x$ be the number of elements in set $A$ that are divisible by $x$ and $DB_x$ be the number of elements in set $B$ that are divisible by $x$.↵
↵
- The number of pairs $a\in A$, $b\in B$ such that $gcd(a,\ b) = 1$ (i.e., $a$ and $b$ are coprime) is: ↵
↵
↵
$$\sum^{U}_{i = 1} DA_i\times DB_i\times F_i\ (^*)$$↵
↵
where $F_i$ is Mobius function in $i$.↵
↵
Is this method correct ? Thanks for your attention, and have a good day (sorry for my bad English btw).↵
↵
Edit: $U$ in $(^*)$ is the maximum value of all elements in $A$ and $B$.
↵
- Let $DA_x$ be the number of elements in set $A$ that are divisible by $x$ and $DB_x$ be the number of elements in set $B$ that are divisible by $x$.↵
↵
- The number of pairs $a\in A$, $b\in B$ such that $gcd(a,\ b) = 1$ (i.e., $a$ and $b$ are coprime) is: ↵
↵
↵
$$\sum^{U}_{i = 1} DA_i\times DB_i\times F_i\ (^*)$$↵
↵
where $F_i$ is Mobius function in $i$.↵
↵
Is this method correct ? Thanks for your attention, and have a good day (sorry for my bad English btw).↵
↵
Edit: $U$ in $(^*)$ is the maximum value of all elements in $A$ and $B$.
