Number of triples of divisors who are relatively prime as a triple

combinatorial-number-theorycombinatoricselementary-number-theorygcd-and-lcmnumber theory

Given a number $n \in \mathbb{N}$, define $a(n)=\{(d_1,d_2,d_3): d_i|n,\ \gcd(d_1,d_2,d_3)=1,\ 1 \leq d_1 \leq d_2 \leq d_3\}$. What is $|a(n)|$?

There were similar questions asked about pairs rather than triples here:
Number of pairs of nontrivial relatively prime divisors and here: Number of Relatively Prime Factors but the addition of the third component seems to make the arguments used in these two questions obsolete.

An example:

Let $n=p$ for some prime $p$. Then the divisors of $n$ are $\{1,p\}$, and the triples of those divisors whom are relatively prime (order does not matter) as a triple are $\{(1,1,1),(1,1,p),(1,p,p)\}$. Thus we see that for any prime, the answer is $|a(n)|=3$.

Similarly, (its not hard to check) for $n=p^2$, we have $|a(n)|=6$.

In fact, if you let $n=p^k$ for $0 \leq k \in \mathbb{Z}$, it seems that $|a(n)|={{k+2} \choose {2}}$.

Also for $n=pq$ where $p$ and $q$ are distinct primes, $|a(n)|=13$ (again, not hard to check).

This leads me to believe that like in the other answers for the two referenced questions, the answer may be found using some nice combinatorics, but if looked at just right from a Number Theoretic perspective, may be a multiplicative function or composition of multiplicative functions, based on how the answers seem to only depend on the powers of the primes in the prime factorization of the number.

Best Answer

As in the pair case, let's first find the number of ordered triples without restrictions on the order of the entries.

Every prime factor $p_i$ with multiplicity $a_i$ occurs in at most two divisors.

There is $1$ way for $p_i$ to occur in zero divisors.

There are $3a_i$ ways for $p_i$ to occur in one divisor.

There are $3a_i^2$ ways for $p_i$ to occur in two divisors.

Thus, in total there are $3a_i^2+3a_i+1$ ways to distribute $p_i^{a_i}$ over the divisors, and hence there are $\prod_i(3a_i^2+3a_i+1)$ ordered triples. From this we want to deduce the number of unordered triples (or, equivalently, the number of ordered triples with the order restrictions on the entries).

There is one triple with three equal entries, namely $(1,1,1)$. There are $\prod_i(2a_i+1)-1$ ordered pairs of distinct coprime divisors, each of which corresponds to three ordered triples with two equal entries but only one unordered triple with two equal entries. Thus the count of unordered triples is

$$ \frac{\prod_i(3a_i^2+3a_i+1)-3\left(\prod_i(2a_i+1)-1\right)-1}6+\prod_i(2a_i+1)-1+1=\frac{\prod_i(3a_i^2+3a_i+1)+3\prod_i(2a_i+1)+2}6\;. $$

You can check that your examples all come out right.

Related Question