# Find numbers with a given number of divisors.

There was a final school exam in Russia recently, "Unified State Exam", that has the following problem in it's most complex chapter, "C":

C6: Find all numbers that end with "$0$" (decimal notation, of course) and have exactly fifteen natural divisors including "$1$" and the number itself.

What could be the solution that involves only school math?

-
..Is $\displaystyle\sigma_0(n)=\prod_{p\mid n}(1+v_p(n))$ school-ie enough? – anon Jul 1 '12 at 6:04
End with "$0$" means that the number must have at least have one divisor of $2$ and one divisor of $5$. The rest follows from the divisor function. – Eugene Jul 1 '12 at 6:04
What's that (sorry for being so dumb)? I mean, that product formula? – mbaitoff Jul 1 '12 at 6:04

We sort of need the link between prime factorization and the number of positive divisors. If $n$ has the prime factorization $p_1^{a_1}\cdots p_k^{a_k}$ then the number of positive factors of $n$ is $\prod (a_i+1)$. In particular the number of divisors is odd iff $n$ is a perfect square.
The fact that the number of divisors is odd iff our number is a perfect square can also be done in a formula-free way by a pairing argument. Any divisor $d$ of $n$ can be paired with the divisor $n/d$, which is different from $d$ unless $d=\sqrt{n}$.
Since $n$ ends in $0$ it has $2$ and $5$ and possibly others as prime factors. But $15$ gives very few possibilities: just two $2$'s and four $5$'s, or the other way around.
The number of positive factors is 15, which is 1*3*5. So, there are no more than 3 prime factors of $n$. Two of them are 2 and 5. How to prove that there's no third divisor? – mbaitoff Jul 1 '12 at 6:16
Baaw, got it. $1=(a_i+1)$. Thus, $a_i=0$. – mbaitoff Jul 1 '12 at 6:17