Number of triplets for which $\gcd(a,b,c)=1$ and $c=n$

Question

As stated in A123323:

Number of triples a,b,c with a<=b<=c<a+b, gcd(a,b,c)=1 and c=n.
......
A123323(n)=sumdiv(n, d, floor((d+1)^2/4)*moebius(n/d))

How to get this formula and how Moebius transformation works? Thanks.

Answer 1

The Möbius function $\mu$ is defined as $$\mu(n) = \cases{0 & \text{if $n$ is not squarefree}\\1 & \text{if $n$ has an even number of prime divisors} \\ -1 & \text{if $n$ has an odd number of divisors}}$$ A priori, it's not immediately obvious why we should study a function such as this. I mean it is rather exotically defined. However, it turns out that this function is deeply connected to many parts of mathematics, in particular number theory and combinatorics, and finds many uses, such as Möbius inversion.

What we will see is that the number of non-degenerate integer triangles is intimately related to the number of coprime integer triangles. We shall see that the two counts are related through Möbius inversion, which is precisely why the Möbius transformation shows up. There are many resources available on Möbius inversion so I will not elaborate on it. Instead, I will jump right into its use.

Note that the floor term in your sum actually counts the total number of non-degenerate$^1$ integer triangles with max side length $c=n$, which we will denote as $g(n)$: $$g(n) = \left\lfloor \frac{(n+1)^2}{4} \right\rfloor$$ Proving this fact will take us too far afield, so I will simply provide a reference.

The key insight here is that each triangle has a particular $\gcd$. Let $f_d(n)$ count the number of integer triangles with max side length $c=n$ and $\gcd(a,b,c) = d$. Then we have the relation $$g(n) = \sum_{d\mid n} f_d(n)$$ This simply says that each triangle has a particular value for its $\gcd$, which necessarily must divide $c=n$. Note that $f_1(n)$ is the value we want, which counts the number of such triangles with coprime sides.

Now, a triangle $(a,b,c)$ has $\gcd(a,b,c)=d$ if and only if the triangle $\left(\frac{a}{d},\ \frac{b}{d},\ \frac{c}{d}\right)$ is coprime. This means that $$f_d(n) = f_1\left(\frac{n}{d}\right)$$ But this allows us to express $g$ solely in terms of $f_1$: $$g(n) = \sum_{d\mid n}f_1\left(\frac{n}{d}\right)$$ This is precisely the condition which allows us to apply Mobius inversion. So we then get $$f_1(n) = \sum_{d\mid n}g(d)\mu\left(\frac{n}{d}\right) = \sum_{d\mid n}\left\lfloor \frac{(d+1)^2}{4} \right\rfloor\mu\left(\frac{n}{d}\right)$$ which is precisely the formula we were after.

$^1$ This sequence actually counts only non-degenerate (i.e. not collapsed into a line) integer triangles with coprime sides. This is required by the strict inequality $c < a+b$. Interestingly, if the inequality were not strict, then you would replace $d+1$ by $d+2$ in the floor function.