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