nhphuc's blog

A question about Mobius function
By nhphuc, history, 10 months ago, In English

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

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nhphuc (previous revision, new revision, compare).

→ Reply