5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Guess I should've had a good look at the link beforehand. I agree with your last line - that makes sense $\endgroup$ – Shuri2060 Jul 8 '17 at 15:40
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd appreciate if someone could check through - I might've easily made an error here as I thought it up on the spot. $\endgroup$ – Shuri2060 Jul 8 '17 at 12:39
  • $\begingroup$ I actually have that exact same thing written down on paper, but also thought it was a little "ugly", so was hoping there was some simplification somewhere. $\endgroup$ – Matthew Crawford Jul 8 '17 at 12:41
  • $\begingroup$ @MatthewCrawford In the end, though, this problem depends solely on the choice of the $a_i$s. *And woops, I keep using $\alpha$ instead of $a$ $\endgroup$ – Shuri2060 Jul 8 '17 at 12:49
  • 1
    $\begingroup$ For $n=30=2^1 3^1 5^1$, this gives you $T=(3)(8)-(8)\left(\frac{3}{2}\right)-(3)=9$, while in the answer below, we see that it should be 6. So whether or not its a simplification, its wrong somewhere. $\endgroup$ – Matthew Crawford Jul 8 '17 at 13:11
  • 1
    $\begingroup$ Could you show an example with your new proof, or perhaps several, with different exponent combinations? $\endgroup$ – Matthew Crawford Jul 8 '17 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.