# How is the Prime Number Decomposition Theorem correctly used?

So I want to find the smallest number with 500 divisors. Using the prime number decomposition theorem is a good way to do this.

The prime number decomposition theorem states:

Every integer $N$ can be structured as a product of powers of prime numbers: $$N=p_1^\alpha p_2^\beta...p_j^\gamma,$$ and the total number of factors of $N$ is $F_N=(\alpha+1)(\beta+1)...(\gamma+1).$

Consider $500$. It can be seen that $500=2\times2\times5\times5\times5=(1+1)(1+1)(4+1)(4+1)(4+1).$ So we can construct an integer which is a product of 5 primes, two of which stand alone, and 3 of which are to the power of 4.

But how can I find the minimum number with 500 divisors? I initially thought to just minimise the product, which means doing:

$$N = 2\times2\times2^4\times2^4\times2^4=16,384.$$ But this is not correct. The correct answer is: $$N=62,370,000=7\times11\times2^4\times 3^4\times 5^4.$$ How are these prime numbers arrived at?

• You've written $N$ as a sum of prime powers, instead of a product, but never mind; the point you've missed is that they have to be distinct primes for the formula to work. They can't all be 2, as you've chosen. aslo, you may find oeis.org/A005179 interesting. – Gerry Myerson Oct 24 '17 at 9:37
• Note that your number can be written as N=2^14 so it has only 15 positive divisors. The correct definition of the Fundamental Theorem of Arithmetic (the prime factorization theorem) states that $p_i≠p_j \forall i≠j$. That's what your definition lacked and thus why you could write your number in such a manner. – Francisco José Letterio Oct 24 '17 at 11:01

There are really two questions here: what did you do wrong, and how do you do it right? What you did wrong was mostly related to your statement of the fundamental theorem of arithmetic. You should have

$$N=\prod_{i=1}^\infty p_i^{k_i}$$

where $k_i$ are nonnegative integers, all but finitely many equal to zero (so this is really a finite product), and $p_i$ are the sequence of all primes (so each one is different). Note that these are being multiplied, not summed. Then your divisor count is $\prod_{i=1}^\infty (k_i+1)$ which is equivalent to what you wrote.

The important thing here is that the $p_i$ need to be distinct; $2^1 \cdot 2^1 \cdot 2^1$ has $4$ divisors, not $16$. The other important thing is that if all you do is throw in another prime factor, you have the most impact when it is a new prime factor that $N$ isn't already divisible by. Specifically you double the number of divisors. Whereas if $k_i=1$, say, then making it $2$ only increases the number of divisors by a factor of $3/2$.

A crude upper bound on the smallest $N$ with at least $M$ divisors is $p_m \#$, where $m=\lceil \log_2(M) \rceil$ and $p\#$ is the primorial function, the product of all primes less than or equal to $p$. Then $p_m\#$ will be a product of $m$ distinct primes, so it will have $2^m \geq M$ divisors. In your example, $m=9$ so $p_m\#=2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23=223092870$, which has 512 divisors.

Now the point is that you can do better by giving the small primes bigger exponents than the large primes. For example, you can take out the factor of 23 and increase the exponent on $2$ to $3$. Previously, $k_9+1$ and $k_1+1$ were both $2$, now they are $1$ and $4$ respectively, so the number of divisors has stayed the same. But $N$ has shrunk, because $4<23$.

You can do this again with $19$ and $3$.

It no longer does you any good to do it with $17$ and $5$, because $25>17$, but that doesn't mean that you have found the optimal solution, you just have to modify more $k_i$ at the same time in order to find a better solution. In particular, since $2=(4/3)(3/2)$, you can make $k_1=4,k_3=2$ and $k_7=0$, obtaining $2^4 \cdot 3^3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13$ which again has 512 divisors, and is smaller because $10<17$.

I think this number, $10810800$, is actually optimal for the problem of finding the smallest number with at least 500 divisors. This number is actually considerably smaller than your solution, but that is because I've allowed for the freedom to have more than 500 divisors, whereas it appears that in your case you must have exactly 500 divisors. This will actually force $N$ to be a fair bit larger because $500$ is evenly divisible by $5$ $3$ times, so you are forced to have three exponents of $4$ (or one of $4$ and one of $24$, or one of $124$). This means the exponents of $3$ and $5$ have to go up to $4$, which multiplies the number by $75$. That's partially canceled out by removing the factor of $13$, but only partially.

To find the required number,we need 5 different prime numbers first of all. And since we want the smallest number so, lets take the first 5 prime numbers which are $2,3,5,7,11$. Also Any Number of the form $N=2^{k_1} 3^{k_2} 5^{k_3} 7^{k_4} 11^{k_5}$ will have 500 divisors if $k_1,k_2,k_3,k_4,k_5 \in \{1,4\}$ and any two $k_i$ equals to $1$ and all others are $4$.So,For the smallest number, we assign large value i.e. $4$ to small prime numbers $2,3,5$ and small value i.e. $1$ to large prime numbers $7$ and $11$. Hence we get the required number.