2
$\begingroup$

Find number of Distinct remainders when $2009$ is divided by all natural numbers.

obviously if we divide $2009$ by numbers greater than $2009$ remainder is $2009$ so we have to find remainders when $2009$ is divided by numbers below it

i have factorized $2009$ as $$2009=7^2 \times 41$$ and number of divisors of $2009$ is $(2+1)(1+1)=6$.

so if $2009$ is divided by all these $6$ divisors remainder is zero.

if $2009$ is divided by any even number the remainder is odd. But how to find distinct remainders for all these remaining numbers?

$\endgroup$
  • 2
    $\begingroup$ We can easily get 0 by 2009 (or a factor). We can easily get $k$ for $1\le k\le 1004$ by taking $2009-k$. We can easily get 2009 itself. And that's it. $\endgroup$ – almagest May 19 '16 at 15:22
2
$\begingroup$

Dividig by $1005,1006,\ldots, 2009$ give us (backwards) all remainders $0,1,2,3,\ldots, 1004$. A larger remainder requires a divisor $>1004$, but we have just tested all of these - except divisors $>2009$, which give us a remainder of $2009$. Hence the $1006$ distinct remainders are the integers from $0$ to $1004$, and $2009$.

$\endgroup$

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.