# A Diophantine equation involving divisor counting function?

While working on a different problem, I stumbled upon the following question. Since number theory is not my primary field, I hope somebody with more expertise in number theory can show me a way out.

Suppose $$n, m$$ are two positive integers, and let $$\sigma_0(n), \sigma_0(m)$$ be the number of divisors of each, respectively. When do we have: $$\sigma_0(n)+\sigma_0(m)=2\sigma_0(\gcd(n, m))+1.$$

In other words, I'm looking for all the solutions above equation. I was able to work out some special cases but had no strategy for the general case. For example, (up to permutations)

• when these two are coprime any solution is of the form $$(1, p)$$ where $$p$$ is some prime.
• The only solutions with $$m=nq$$ and $$\gcd(n,q)=1$$ are also of the above form.
• Also, $$(p^c, p^{c+1})$$ are solutions.
• In general, one of the integers must be a perfect square, while the other is not.

Likewise, I found some solutions/conditions. What are the solutions in general?

• Btw, I suspect that all the solutions are of the form $(p^n, p^{n+1}).$ Commented Jul 18 at 16:13
• Your first bullet point is wrong. For example $~n = 6, ~m = 35~$ are coprime. The correction to the first bullet point is $$[ ~\sigma(n) - 1 ~] + [ ~\sigma(m) - 1 ~] + 1 = \sigma(n) + \sigma(m).$$ This is explained by reasoning that since $~n,m~$ are coprime, they only share the common factor of $~1.$ Commented Jul 18 at 18:45

For positive integers $$a$$ and $$b$$, consider $$ab$$. If $$b = 1$$, then $$\sigma_0(ab) = \sigma_0(a)$$. However, if $$b \gt 1$$, then all divisors of $$a$$ are also divisors of $$ab$$, but not all of them, so $$\sigma_0(ab) \gt \sigma_0(a)$$. Also, by definition, $$\gcd(n,m) \mid n$$ and $$\gcd(n,m) \mid m$$. This means that

$$\sigma_0(ab) \ge \sigma_0(a) \;\;\to\;\; \sigma_0(n) \ge \sigma_0(\gcd(n, m)), \; \sigma_0(m) \ge \sigma_0(\gcd(n, m))$$

$$\sigma_0(n) + \sigma_0(m) = 2\sigma_0(\gcd(n, m)) + 1$$

we have from the first set of equations that $$\sigma_0(n) + \sigma_0(m) \ge 2\sigma_0(\gcd(n, m))$$, so the above equation requires that either $$\sigma_0(n) = \sigma_0(\gcd(n, m))$$ or $$\sigma_0(m) = \sigma_0(\gcd(n, m))$$, with the other value being one larger. WLOG (due to symmetry), have

$$\sigma_0(m) = \sigma_0(\gcd(n, m)) \;\;\to\;\; \gcd(n, m) = m$$

so $$m \mid n$$ with $$n \gt m$$, i.e., $$n = km$$ for some integer $$k \gt 1$$. This then means that

$$\sigma_0(km) = \sigma(m) + 1$$

If $$m = 1$$, then $$k = p$$ for some prime $$p$$, as indicated in your first set of solutions. Otherwise, with $$m \gt 1$$, then $$m$$ has at least one prime factor, so $$\sigma_0(m) \ge 2$$. If $$k$$ has any prime factors not in $$m$$, then due to the multiplicative nature of the divisor function, we get $$\sigma_0(km) \ge 2\sigma_0(m) \gt \sigma_0(m) + 1$$, which is not possible.

Thus, all prime factors of $$k$$ are also ones of $$m$$. If $$m$$ has $$2$$ or more prime factors, we then have for some integer $$j \ge 2$$ the distinct primes $$p_i$$, plus integers $$a_i \ge 1$$ and $$b_i \ge 0$$, with

$$m = \prod_{i=1}^{j}p_i^{a_i}, \;\; km = \prod_{i=1}^{j}p_i^{a_i + b_i}$$

where at least one $$b_i \ge 1$$, say for index $$r$$. We then have

$$\sigma_0(km) \ge \sigma_0(m) + b_r\sigma_0\left(\prod_{i=1, \, i\neq r}^{j}p_i^{a_i}\right) \ge \sigma_0(m) + 2$$

Thus, there are no solutions for this case. This means that $$m$$, and thus also $$km$$, can have only one prime factor. As such, then $$m = p^{s}$$ and $$km = p^{t}$$ for non-negative integers $$s$$ and $$t$$, so

$$\sigma_0(km) = t + 1 = \sigma_0(m) + 1 = (s + 1) + 1 \;\;\to\;\; t = s + 1$$

This shows that your comment, re: that all of the solutions are of the form $$(p^c, p^{c+1})$$, for primes $$p$$ and integers $$c \ge 0$$ (note I'm using $$c$$ instead of $$n$$ to avoid reusing $$n$$ from your original equation), is correct.

• @Bumblebee You're welcome. I added some more detail to my answer, which I hope better explains how I got $\sigma_0(m) = \sigma_0(\gcd(n,m))$. In particular, since the RHS is just $1$ more than double the $\sigma_0$ value of the $\gcd$, then due to the first set of equations in my answer, we get that one of $\sigma_0(m)$ and $\sigma_0(n)$ must be $\sigma_0(\gcd(n,m))$. Due to the symmetry, I chose WLOG this to be $\sigma_0(m)$. Please let me know if there's anything still unclear about this, and if there's anything else you'd like me to explain further. Commented Jul 18 at 17:17
• Looks great! Thank you very much for your detailed explanation. Commented Jul 18 at 17:19
• @Bumblebee Thanks for clarifying. That makes more sense than what I suggested. Regarding the value of $l$, and all $t$ such that $f_n(t)=l$, since we want $\sigma_0(\gcd(n,t))$ to be quite large, but with ideally with $\sigma_0(t)$ to be relatively small, I suspect (although I haven't given it too much thought) that the minimum $l$ occurs where $t\mid n$, so $\gcd(n,t)=t$, and $f_n(t)$ becomes $\sigma_0(n)-\sigma_0(t)$. Thus, we want to maximize $t$, with this occurring where $t=\frac{n}{q}$ for some prime $q\mid n$, with the exponent of $q$ in $n$'s factorization being the largest. ... Commented Jul 18 at 18:34
• @Bumblebee (cont.) Nonetheless, I'm not sure, including including that even if this does give the smallest $l$, if there are any other values of $t$ where $f_n(t)=l$. Since what you're asking about is quite a bit different than your question here, and the corresponding answer(s) may be relatively long and involved, I suggest you post it as a separate question. Commented Jul 18 at 18:38
• See here for the new question. Commented Jul 19 at 5:39