A question about Mobius function

Правка en2, от nhphuc, 2025-07-12 19:17:08

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский nhphuc 2025-07-12 19:17:08 83 Tiny change: 'is the max value of ' -> 'is the maximum value of '
en1 Английский nhphuc 2025-07-12 18:23:24 595 Initial revision (published)