Numbers from 1 to 1985 are written one after another so they form a new number, $n=123456\ldots19841985$. Prove that there can't be 985 divisors of $n$.

This should be solved on paper, without using programming methods.

  • 1
    $\begingroup$ Do you mean there can't be exactly $985$ divisors, or there can't be at least that many? $\endgroup$ – Chris Eagle Feb 15 '12 at 19:28
  • $\begingroup$ It's actually unclear, but my guess goes for exactly. $\endgroup$ – Lazar Ljubenović Feb 15 '12 at 19:30

Assuming you mean there can't be exactly $985$ distinct divisors of $n$... $985=5\times 197$. If $n=p_1^{a_1}\cdots p_r^{a_r}$, with $p_1\lt\cdots\lt p_r$ primes, then the number of divisors of $n$ is $(a_1+1)\cdots(a_n+1)$, so the only way $n$ could have exactly $985$ divisors is if $n=p_1^4p_2^{196}$ for two distinct primes $p_1$ and $p_2$; or $n=p^{984}$ with $p$ a prime.

Since $n$ is divisible by $5$, one of the primes must be $5$; hence, $n$ would be divisible by $25$. However, all multiples of $25$ end in $00$, $25$, $50$, or $75$, which $n$ does not; so $n$ cannot have exactly $985$ distinct divisors.

Robert Israel rightly points out the much simpler argument: $n$ is divisible by $5$ but not $5^2$, so from the formula for number of divisors we immediately see that the number of divisors of $n$ is even, hence not $985$. And even if you don't know the formula for divisors, you can partition the divisors into multiples of $5$ and coprime to $5$, and pair them up to see the number of divisors is even.

  • 10
    $\begingroup$ Maybe slightly more simply: the number $n$ is divisible by $5$ but not by $25$. Any such number has an even number of divisors, because they occur in pairs: if $d$ is not divisible by $5$, $d$ divides $n$ if and only if $5d$ divides $n$. $\endgroup$ – Robert Israel Feb 15 '12 at 19:42
  • $\begingroup$ @Robert: Of course; that's much simpler... <chagrin>. (Or you can just use the formula I mentioned, since you'll have $5$ in the prime factorization, so $2$ as a factor of the number of divisors...) $\endgroup$ – Arturo Magidin Feb 15 '12 at 19:43
  • 4
    $\begingroup$ Or else, a variant of Robert Israel's solution, only perfect squares have an odd number of divisors. $\endgroup$ – André Nicolas Feb 15 '12 at 19:49
  • $\begingroup$ By the way, $n$ is also divisible by $3$ but not by $9$, so its number of divisors is divisible by $4$. $n/15$ is a composite number of $6831$ digits, probably too big for current technology to factor. $\endgroup$ – Robert Israel Feb 15 '12 at 19:50
  • 1
    $\begingroup$ @sven.hedin: The sum of the digits is the same as the sum of the numbers $1$ through $1985$, which is given by $\frac{(1985)(1986)}{2}$. The numerator is congruent to $5\times 6 = 3$ modulo $9$, hence the numerator is divisible by $3$ but not by $9$. $\endgroup$ – Arturo Magidin Feb 15 '12 at 21:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.