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

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?

• 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. – almagest May 19 '16 at 15:22

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$.