The number of pairs $(m,n)$ of coprime positive integers that divide $k$ is $d(k^2)$, where $d$ is the divisor counting function.

Question

I recently found somewhere that, if $k$ is a fixed integer.Then the number of ordered pairs of positive integers $(m,n)$ such that they are coprime and both of them divide $k$ is $d(k^2)$, where $d$ denotes "the number of divisor function."I tried but was unable to prove it. I thought there might be some bijection between them but failed to prove it.

Answer 1

Let the count of admissible pairs for $k$ be $F(k)$. Following lulu's hint in comments:

• For $k=p^n$ a prime power, admissible pairs can only be $(1,p^z)$ and $(p^z,1)$, $0\le z\le k$. There are $2k+1$ such pairs and $\tau(k^2)=\tau(p^{2n})=2k+1$.
• Let $F(a)=\tau(a^2),F(b)=\tau(b^2)$ and $\gcd(a,b)=1$. Let $(a_1,a_2)$ be an admissble pair for $a$, and similarly for $(b_1,b_2)$ and $b$. Then $(a_1b_1,a_2b_2)$ is an admissible pair for $ab$ since $a_1,a_2,b_1,b_2$ are pairwise coprime. Furthermore, any admissible pair for $ab$ can be uniquely decomposed into a pair for $a$ and a pair for $b$ by matching prime factors; for example, if $a=21$ and $b=10$, the pair $(14,15)$ which is admissible for $ab$ is decomposed into $(7,3)$ for $a$ and $(2,5)$ for $b$. Thus $$F(ab)=F(a)F(b)=\tau(a^2)\tau(b^2)=\tau((ab)^2)$$ where we have used the multiplicative property of $\tau$.

This shows that $F(k)=\tau(k^2)$ for all positive $k$.

Answer 2

For each positive integer $K$, let $D(K)$ denote the set of all positive integers that divide $K$, and $S(K)$ the set of all pairs $(M,N)$ of relatively prime positive integers that divide $K$. For a given positive integer $k$, we shall establish a bijection $f:D(k^2)\to S(k)$ along with its inverse $g:S(k)\to D(k^2)$. Let $$k=p_1^{r_1}p_2^{r_2}\cdots p_l^{r_l}\,,$$ where $p_1,p_2,\ldots,p_l$ are distinct prime natural numbers, and $r_1,r_2,\ldots,r_l$ are positive integers.

Each $s\in D(k^2)$ is of the form $s=p_1^{t_1}p_2^{t_2}\cdots p_l^{t_l}$, where $t_i$ is an integer such that $$0\leq t_i \leq 2r_i\text{ for every }i=1,2,\ldots,l\,.$$ Define $$\mu(s):=\prod_{\substack{i\in\{1,2,\ldots,l\}\\ t_i\leq r_i}}\,p_i^{t_i}\text{ and }\nu(s):=\prod_{\substack{i\in\{1,2,\ldots,l\}\\ t_i> r_i}}\,p_i^{t_i-r_i}\,.$$ Note that $\mu(s)$ and $\nu(s)$ are divisors of $k$ and $\gcd\big(\mu(s),\nu(s)\big)=1$. Therefore, if we set $$f(s):=\big(\mu(s),\nu(s)\big)$$ for each $s\in D(k^2)$, then $f:D(k^2)\to S(k)$.

Suppose now that $(m,n)\in S(k)$. Write $$n=p_1^{\beta_1}p_2^{\beta_2}\cdots p_l^{\beta_l}\,,$$ where $\beta_i$ is an integer such that $$0\leq \beta_i\leq r_i\text{ for each }i=1,2,\ldots,l\,.$$ Define $$g(s):=m\,\prod_{\substack{i\in\{1,2,\ldots,l\}\\\beta_i>0}}\,p_i^{r_i+\beta_i}\,.$$ Then, clearly, $g:S(k)\to D(k^2)$ is the inverse function of $f$. Thus, $$\sigma_0(k^2)=\big|D(k^2)\big|=\big|S(k)\big|\,.$$ (I prefer the notation $\sigma_0$, instead of $d$.)

Remark. In general, for any positive integer $t$, $\sigma_0(k^t)$ is the number of tuples $(n_1,n_2,\ldots,n_t)$ of pairwise relatively prime positive integers such that $n_j$ is a divisor of $k$ for all $j=1,2,\ldots,t$. My proof for the case $t=2$ can be extended easily to the general situation. A more difficult question is: what is the number of tuples $(n_1,n_2,\ldots,n_t)$ of positive integers such that $n_j$ is a divisor of $k$ for all $j=1,2,\ldots,t$, and $\gcd(n_1,n_2,\ldots,n_t)=1$?