Number of pairs of nontrivial relatively prime divisors

Question

Given a number, $n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, how many pairs of divisors (excluding 1) that are relatively prime are there?

For example: $n=2^2\cdot 3=12$. There are 6 distinct factors:$\{1,2,3,4,6,12\}$, and the only pairs of factors that are relatively prime to each other (excluding 1 of course) are $\{2,3\}$ and $\{2^2,3$}.

There was a similar question posted some years ago: Number of Relatively Prime Factors.

My thoughts are that it is the $\frac{P-1}{2}$ mentioned before, but removing the $(\tau(n)-1)$ pairs with 1 in them (where $\tau$ is the number of divisors function), making for a total of $\frac{P-1}{2}-\tau(n)+1$.

Answer 1

At first let me change the question a bit, we will modify it to your original question at the end.

In counting such pairs we will make difference between the pairs $(a,b)$ and $(b,a)$; i.e. we will count $(a,b)$ and $(b,a)$ as 2 different pairs, (except for the case $(a,b)=(1,1)$).

Also let $1$ to be a legal choice for the value of $a$ or $b$. For example when $n=12$ we have the following pairs:

(2,3), (3,2),

(4,3), (4,3),

(1,12), (1,6), (1,4), (1,3), (1,2), (1,1),

(12,1), (6,1), (4,1), (3,1), (2,1).

---

---

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ as you let, and let $(a,b)$ to be satisfied in the above conditions, and let $a=p_1^{\gamma_1}p_2^{\gamma_2}...p_k^{\gamma_k}$ and $b=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$. Fix a prime number which divides $n$, for example $p_i$.

---

---

Three cases may occure:

• $p_i\nmid a$ and $p_i\nmid b$:

in this case we have $\beta_i=\gamma_i=0$, so in this case we have only one choice for the pair $(\beta_i,\gamma_i)$.

• $p_i\mid a$ and $p_i\nmid b$:

in this case we have $\gamma_i=0$, $1\leq \beta_i \leq \alpha_i$; so in this case we have $\alpha_i$ choices for the pair $(\beta_i,\gamma_i)$.

• $p_i\nmid a$ and $p_i\mid b$:

in this case we have $\beta_i=0$, $1\leq \gamma_i \leq \alpha_i$; so in this case we have $\alpha_i$ choices for the pair $(\beta_i,\gamma_i)$.

• $p_i\mid a$ and $p_i\mid b$: this case is impossible.

So in all we have $2\alpha_i+1$ choices for choosing $\beta_i$ and $\gamma_i$.

---

---

So we have $\prod_{i=1}^{k}(2\alpha_i+1)$ relatively prime pairs in the changed problem, but notice that in the original problem the pairs $(1,d)$ and $(d,1)$ are not legal. The number of illegal pairs of the form $(1,d)$ is equal to $\prod_{i=1}^{k}(\alpha_i+1)$; similarly the number of another illegal pairs is equal to $\prod_{i=1}^{k}(\alpha_i+1)$. But these pairs have a common pairs $(a,b)=(1,1)$, so number of the illegal pairs are equal to $2\Bigg(\prod_{i=1}^{k}(\alpha_i+1)\Bigg)-1$.

So we have $\prod_{i=1}^{k}(2\alpha_i+1)-2\Bigg(\prod_{i=1}^{k}(\alpha_i+1)\Bigg)+1$ legal pairs. But remember that we count $(a,b)$ and $(b,a)$ as 2 different pairs, so we must divide the last formula by 2.

---

So the answer to your original problem is equal to:

$1/2\Bigg(\prod_{i=1}^{k}(2\alpha_i+1)+1\Bigg)-\Bigg(\prod_{i=1}^{k}(\alpha_i+1)\Bigg)$.

Notice that the second term is equal to the number of divisors of $n$ and the first term is equal to the number of divisors of $n^2$ plus one, divided by 2.

So the formula changes to $1/2\Bigg(d(n^2)+1\Bigg)-d(n)$, where $d(m)$ stands for the number of divisors of $m$.

Answer 2

This is more a help than an answer. Let $N=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, we have, that the number of divisors total is $(a_1+1)(a_2+1)\ldots (a_k+1)$. We also know, that 1 and N, are divisors we don't want to look at. Any powers of $p_i$are divisible by by $p_i$. It follows, that when considering pairs, that we exclude at least one set of powers. To get what I mean, lets consider $30=2^13^15^1$ has 8 divisors 2 of which we won't even consider. Eliminating one set of powers for comparison, we have $(2\times 2)-1$ divisors in the powers left that aren't 1. We have, 1 power of the prime left out, that's not equal to 1. So, we have, 3 for that power to match up with. We have, three primes that could have been. So we have 9 divisor pairings if any one prime is left out. These are: (2,3),(2,5),(2,15),(3,2),(3,5),(3,10),(5,2),(5,3),(5,6). Now of course, there are duplicates, if you don't care for the order of a pair. You can always reorder the pairs, and get that there's 3 distinct ones using the highest divisor, that can't change in this case. In the rest, there are two ways of ordering so 9-3=6; and 6/2=3; so 3+3=6, which is the list: (2,3),(2,5),(2,15),(3,5),(3,10),(5,6).

Answer 3

My attempt, although it yields an answer which isn't very nice

---

Take a particular set $F=\{i:1\le i\le k\}$.

Let us find the number of factors which are coprime to $\prod_{i\in F}p_i$.

For any divisor $d$ and $b_1,...,b_j \in\mathbb N_0,\,\,\, (\forall i)\,\,\,b_i\le a_i$,

$$\gcd\left(d\,\,\,,\,\,\,\prod_{i\in F}p_i\right)=1 \iff d=\prod_{i\not\in F} p_i^{b_i}$$

$\implies$ (set of all possible divisors $\neq1$ which are coprime to the product of primes indexed by $F$)

$$\left|\left\{d\neq1:(d\,\,|\,\,n)\land\gcd\left(d\,\,\,,\,\,\,\prod_{i\in F}p_i\right)=1\right\}\right|=\left(\prod_{i\not\in F} (a_i+1)\right)-1$$

Now, for $b_1,...,b_n \in\mathbb N_0$,

$$\gcd\left(\prod_{i\in J} p_i, x\right)=1 \iff \gcd\left(\prod_{i\in J} p^{b_i}, x\right)=1,$$

$\implies$ (set of all possible pairs with $f$ being composed only of primes indexed by $F$)

$$\left|\left\{(d,f):(d\,\,|\,\,n)\land(b_1,...,b_{|F|} \in\mathbb N_0,\,\,\, (\forall i)\,\,\,b_i\le a_i)\land\left(f=\prod_{i\in F}p_i^{b_i}\right)\land(\gcd\left(d,f\right)=1)\right\}\right|=\left(\left(\prod_{i\in F} (a_i+1)\right)-1\right)\left(\left(\prod_{i\not\in F} (a_i+1)\right)-1\right)$$

$$=\prod^k_{i=1}{(a_i+1)}-\prod_{i\in F}{(a_i+1)}-\prod_{i\not\in F}{(a_i+1)}+1$$

Now, we are interested in $\left|\left\{\{d,f\}:(d\,\,|\,\,n)\land(f\,\,|\,\,n)\land(\gcd(d,f)=1)\right\}\right|$. We can find this by summing the above over all possible sets $F$, but we have to take into account that everything is counted twice as we are after unordered pairs.

So the final answer, $T$, is

$$T=\left|\left\{\left\{d,f\right\}:(d\,\,|\,\,n)\land(f\,\,|\,\,n)\land(\gcd(d,f)=1)\right\}\right|=\frac{1}{2}\left|\left\{(d,f):(d\,\,|\,\,n)\land(f\,\,|\,\,n)\land(\gcd(d,f)=1)\right\}\right|$$

$$=\frac{1}{2}\sum_{F\neq\varnothing\subset\{1,...,k\}} \left(\prod^k_{i=1}{(a_i+1)}-\prod_{i\in F}{(a_i+1)}-\prod_{i\not\in F}{(a_i+1)}+1\right)$$

Let $P=\prod^k_{i=1}(a_i+1)$. Then

$$T=\frac{1}{2}\left(\left(2^k-2\right)(P+1)-\sum_{F\neq\varnothing\subset\{1,...,k\}}\left(\prod_{i\in F}{(a_i+1)}+\prod_{i\not\in F}{(a_i+1)}\right)\right)$$

$$=\left(2^{k-1}-1\right)(P+1)-\frac{1}{2}\sum_{F\neq\varnothing\subset\{1,...,k\}}\left(\prod_{i\in F}{(a_i+1)}+\prod_{i\not\in F}{(a_i+1)}\right)$$

$$=\left(2^{k-1}-1\right)(P+1)-\sum_{F\neq\varnothing\subset\{1,...,k\}}\prod_{i\in F}{(a_i+1)}$$

$$=2^{k-1}(P+1)-\sum_{F\subseteq\{1,...,k\}}\prod_{i\in F}{(a_i+1)}$$

Not sure on simplifying it further. It seems this question, Elementary symmetric polynomials and Newton's Identities are related

---

Example calculations:

$n=30=2^13^15^1\implies k=3, P=8, (\forall i)\,\,a_i+1=2$

So, observing that there are $2^k-2=6$ possible subsets, which all are size $1$ or $2$,

$$T=27-(3(2)+3(4))=9$$

Not sure how more complicated examples can be done without a computer for verification.

---

I'm not so sure this particular answer relates to $$P=\prod_{i=1}^k(2a_i+1)$$ from the link.