10
$\begingroup$

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
    Do you mean there can't be *exactly* $985$ divisors, or there can't be *at least* that many?2012-02-15
  • 0
    It's actually unclear, but my guess goes for _exactly_.2012-02-15

1 Answers 1

19

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
    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$.2012-02-15
  • 0
    @Robert: Of course; that's *much* simpler... . (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...)2012-02-15
  • 4
    Or else, a variant of Robert Israel's solution, only perfect squares have an odd number of divisors.2012-02-15
  • 0
    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.2012-02-15
  • 0
    @RobertIsrael How did you find $n$ is divisible by $3$ but not by $9$? By summing the digits?2012-02-15
  • 1
    @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$.2012-02-15
  • 0
    @ArturoMagidin Got it. I think you mean sum of digits and sum of numbers $1$ through $1985$ are same modulo $3$ and $9$.2012-02-15
  • 0
    @sven.hedin: Yes. Good catch.2012-02-15