0
$\begingroup$

Let n be a positive integer less than 1000. If n^3 has 10 factors, compute the largest value of n.

  • 1
    Note that $n$, not $n^3$, is less than $1000$2011-10-27

1 Answers 1

3

The following result is useful in contests, and elsewhere. Let $p_1, p_2, \dots,p_k$ be distinct primes, let $e_1, e_2,\dots, e_k$ be positive integers, and let $N=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}.$ Then $N$ has $(e_1+1)(e_2+1)\cdots (e_k+1).$ positive divisors. For example if $N=2^3\cdot 3 \cdot 5^2$, then $N$ has $(4)(2)(3)$ positive divisors.

Now we use the above result to answer the question. Note that a cube has prime power decomposition of shape $p_1^{3a_1}p_2^{3a_2}\cdots p_k^{3a_k}$. If this cube has $10$ divisors, we have $(3a_1+1)(3a_2+1)\cdots(3a_k+1)=10.$ The only way this can happen is if $k=1$, and $a_1=3$. Thus your number $n$ has the shape $p^3$ where $p$ is prime. We want to find the largest prime $p$ such that $p^3<1000$. This prime is $7$, and therefore $n=7^3=343$.

Comment: Here is a brief informal proof of the key result. Imagine we are building a positive divisor $d$ of $N$. How many possible choices are there for the largest power of $p_1$ that divides $d$? That largest power could be any of $p_1^0$ (no $p_1$'s), $p_1^1$, and so on up to $p_1^{e_1}$, so we have $e_1+1$ choices.

For every one of these choices, we have $e_2+1$ choices for the highest power of $p_2$ that divides $d$, and therefore $(e_1+1)(e_2+1)$ ways to choose the largest power of $p_1$ that divides $d$ and the largest power of $p_2$ that divides $d$. But for every one of these choices, there are $d_3+1$ ways to choose the highest power of $p_3$ that divides $d$, and so on.

  • 0
    It's quite useful when solving computer problems too (e.g. [Project Euler](http://projecteuler.net/)) - this formula often leads to more efficient methods for calculating the factors of a number.2011-10-27