# Solution to "Product Pairs"

The number of divisors $d$ for some number $n$ with prime factorization $p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ where $p_1,p_2,\dots,p_k$ are distinct primes, is given by

In other words, you take the exponents, add one, and multiply. (This can be shown easily enough if you view each distinct prime as a certain color ball, then for each color ball you can choose either none of them, or one, or two, or ..., up to $a_i$; then each color of ball can be chosen $a_i+1$ ways, the product of which gives you the total ball groupings possible.) So for example, $12=2^2\cdot 3^1$ should have $(2+1)(1+1)=6$ divisors (including $1$ and itself). The divisors of $12$ are $1,2,3,4,6,12$, which number $6$.

Then for each divisor, it has another divisor to which it multiplies to give the number. For instance, the $1$ is paired with $12$, $2$ with $6$, and so on. Then the total number of pairs in the example for $12$ would be $6/2=3$. The exception is when a number is a square, in which case it would have an odd number of divisors, the one in the middle when ordered would be the square root. For instance, the divisors of $16$ are $1,2,4,8,16$, the middle number being paired with itself.

So in order to have exactly $40$ pairings as described in the problem, we need the divisor function to give us either $80$ divisors, or $79$ divisors. Then the increment of each exponent in the prime factorization of such a number must multiply together to give us $80$ or $79$. Thus our goal is to see how many ways we can make a product of $79$ or $80$, then set those factors (minus $1$) as the exponents to primes, and see which one is the smallest.

Then what are all the ways to make $80$ or $79$? We build quite an extensive list, and I will write them in the form $\{ x_1,x_2,\dots\}$, meaning that $x_1\cdot x_2\cdots=80\text{ or }79$. Of course $79$ is prime so there is only one way to make it, so I will make it first in the list, followed by ways to make $80$.

I believe that is all the ways to get either $79$ or $80$ when multiplied, then the sets of exponents will be all these minus $1$, giving us

The number we are looking for must have these exponents in its factorization, and since we are looking for the smallest number, the smallest prime will be assigned the highest exponent, and then we can easily compare two by two until we have the victor. For odd numbers, the smallest prime is $3$, and after comparing the resulting numbers, we discover that $\{ 1, 1, 1, 1, 4\}$ results in the smallest odd number $3^4\cdot 5\cdot 7\cdot 11\cdot 13=405405.$ Then the smallest odd number with exactly $40$ "product pairs" is $405405$.

The same process is done for even numbers with the only difference being that the smallest prime factor is $2$, therefore we take each exponents set, assign them in decreasing order to increasing primes, and compare them with each other. In this case the smallest value comes out from the set $\{ 1,1,3,4\}$ to be $2^4\cdot 3^3\cdot 5\cdot 7=15120$. So the smallest even number, actually smallest positive number altogether which can be factored into exactly $40$ product pairs is $15120$.