3
$\begingroup$

How can I get started on this proof? I was thinking originally:

Let $ n $ be odd. (Proving by contradiction) then I dont know.

$\endgroup$
  • 7
    $\begingroup$ It may help to try proving the stronger "Let $d > 1$. Then the smallest positive integer having $d$ divisors is even." $\endgroup$ – Daniel Fischer Dec 19 '14 at 14:00
  • $\begingroup$ @EuroMicelli $2^{n-1}$ actually. $\endgroup$ – Najib Idrissi Dec 19 '14 at 16:09
  • $\begingroup$ @EuroMicelli Is the smallest number with one (positive) divisor $1$ or $2$? Is the smallest number with two divisors $2$ or $4$? $\endgroup$ – Najib Idrissi Dec 19 '14 at 16:25
  • $\begingroup$ Wouldn't the smallest positive number with 500 divisors just be 2^500? $\endgroup$ – GMA Dec 19 '14 at 18:34
  • 1
    $\begingroup$ @GeorgeMillo: $62370000$ is rather smaller than $2^{499}$, both of which have $500$ divisors. $841824943102600080885322463644579019321817144754176$ is rather smaller than $2^{500}$, both of which have $500$ proper divisors. $14414400$ is smaller than any of these and has $504$ divisors. $\endgroup$ – Henry Dec 20 '14 at 1:42
18
$\begingroup$

Hint: Try to construct the smallest number with $k>1$ divisors. If it does not have $2$ as a divisor, can it be the smallest?

$\endgroup$
20
$\begingroup$

If $n$ is odd, let $p$ be its smallest prime divisor, and $p^r$ the greatest power of $p$ that divides $n$. Then, the number $$\frac{2^rn}{p^r}$$ has the same number of divisors, it is smaller than $n$ and it is even.

$\endgroup$
  • 1
    $\begingroup$ Nice answer! +1 ... Just some nitpicking: $p$ only exists if $n>1$ (the case $n=1$ trivially doesn't have $500$ divisors), and $p \neq 2$ because $n$ is odd $\endgroup$ – Zubin Mukerjee Dec 19 '14 at 14:04
3
$\begingroup$

Let $n$ be the smallest positive number that has $k>1$ divisors and let $n=p_1^{r_1}\times\cdots\times p_s^{r_s}$ be its factorization in primes. If $n$ is odd then $2<p_i$ for $i=1,\dots,s$. Replacing one of the $p_i$ by $2$ results in a smaller number that has the same number of divisors ($k=r_1\times\cdots\times r_s$) so a contradiction is found.

$\endgroup$
3
$\begingroup$

To get you started

Assume that the largest number that is divisible by 500 different numbers is $n$, then assume $n$ is not divisible by $2$. and is instead divisible by $x$, which is the smallest positive integer than $n$ can be divided by, hence $x$ must be larger than 2.

To finish the proof (so do not read if you just want to get started)

we find that $\frac{n*2}{x}$ is divisible by 2 and is smaller than $n$, hence $n$ cannot be the smallest number divisible by 500 different numbers

$\endgroup$
2
$\begingroup$
  • The smallest number with at least $500$ divisors is $2^6\times 3^2 \times 5^2 \times 7 \times 11 \times 13 = 14414400$

  • The smallest number with at exactly $500$ divisors is $2^4\times 3^4 \times 5^4 \times 7 \times 11 = 62370000$

  • The smallest number with at exactly $500$ divisors apart from itself is $2^{166}\times 3^2 = 841824943102600080885322463644579019321817144754176$

All three of these are even.

$\endgroup$
  • $\begingroup$ Is there a nice method of reaching these or is it going through a lot of calculation? $\endgroup$ – Aaron Dec 20 '14 at 16:49
  • $\begingroup$ Some are easier than others. For example the third case here requires considering that the prime factorisation of $501$ is $3 \times 167$, so the only numbers with exactly $501$ divisors ($500$ divisors apart from themselves) are either of the form $p_1^{500}$ or of the form $p_1^{166}\times p_2^{2}$ with $p_1$ and $p_2$ distinct primes, and it is easy to find the smallest example. The others are similar but more effort. $\endgroup$ – Henry Dec 20 '14 at 17:33
  • $\begingroup$ @Aaron: the number of divisors of $n$, denoted $d(n)$ in number theory (and including both $1$ and $n$, thank you very much), has a formula. $d( p_1^{n_1}\cdots p_k^{n_k} ) = (n_1+1)\cdots (n_k+1)$. This formula is a relatively straightforward consequence of unique factorization, and it helps a lot! BTW, like a number of important such functions it is "multiplicative" in that $d(ab) = d(a) d(b)$ IF $a$and and $b$ are relatively prime, i.e. $(a,b)=1$. This is one reason why, by convention, 1 and n counted as divisors of n. $\endgroup$ – Nat Kuhn Dec 20 '14 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy