2

Let $a$ and $b$ be the number of divisors of two positive integers , is it possible to explicitly express the number of divisors of their product only in terms of $a$ and $b$? If not , how can it be calculated efficiently without actually calculating the product?

Narek Margaryan
  • 1,066
  • 1
    The number-of-divisors function $\sigma_0$ is multiplicative, which means $\sigma_0(nm)=\sigma_0(n)\sigma_0(m)$ if $n,m$ are coprime. The number $\sigma_0(nm)$ is not generally determined by that of $\sigma_0(n)$ and $\sigma_0(m)$ though. – anon Dec 29 '13 at 09:32

4 Answers4

1

Let the number of divisors function be $d$. Then, it is known that $$ d(mn) = d(m) \cdot d(n), $$ for $\operatorname{gcd}(m,n)=1$. That is, $d$ is multiplicative for relatively prime inputs. But not in general.

Rich_Rich
  • 430
Ahaan S. Rungta
  • 7,706
1

The answer is no.You just can't express it in terms of a and b.

I'm telling you a general method through an example.

Let Numbers is 20.

$20 = 2^25^1$ Number of divisors = (2+1)(1 + 1) = 6

So number of divisors of $a_1^{p_1}a_2^{p_2}...a_n^{p_n} = (p_1 + 1)(p_2+1)...(p_n+1)$ where $a_1,a_2,...,a_n$ are prime numbers.

These are total number of divisors (including 1 and the number itself).

user2369284
  • 2,231
  • Very nice, but if the logic were there too, then would be great for beginners like m to understand. – jitender Feb 03 '18 at 23:06
0

If $a,b$ are coprime, yes and the answer is $ab.$ In general, I don't think there is such expression.

Consider the $(12,4)$ case :

$12=2^2\cdot 3^1$ has $(2+1)(1+1)=6$ divisors, and $4=2^2$ has $2+1=3$ divisors.

On the other hand, $12\cdot 4=48=2^4\cdot 3^1$ has $(4+1)(1+1)=10$ divisors.

mathlove
  • 139,939
0

If $a$ and $b$ are relatively prime, then the number of divisors of $ab$ is the product of the number of divisors of $a$ and the number of divisors of $b$. If they are not, then the relationship could be a lot more subtle.

You'd be better off using the explicit formula for the number of divisors in the general case. If $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, then $d(n) = (a_1+1)(a_2+2)\cdots (a_k+1)$. Finding the number of divisors of a product of two numbers, if they aren't relatively prime, involves looking at this formula to figure out which factors need to change and how, for any primes that divide both.

Andrew Dudzik
  • 30,074