# Divisibility problem.

In line written squares of natural numbers from 1 to 2012. How many of these numbers have a remainder when divided by 17, which is divisible by 3?

Hint: make a list of the squares of the numbers $0$ through $16$ and compute the remainder on dividing by $17$. See how many and which ones they are. There are $\lfloor \frac {2102}{17} \rfloor=118$ complete cycles and a bit.
• @DanSh: The idea is that if $m^2$ has a remainder divisible by $3$ when divided by $17,$ so will $(m+17k)^2=m^2+34mk+289k^2$ because the last two terms are divisible by $17$ – Ross Millikan Apr 29 '13 at 21:18
• Still do not understand. what can i get from $(m+17k)^{2} = m^{2} + 34mk + 289k^{2}$? the last two terms are divisible, this is okey, but it is my start conditions, that $m^{2}$ must be divided by 17. – Dan Sh Apr 30 '13 at 20:03
• @DanSh: It means that the cycle will repeat every $17$. Just as $10^2 \equiv 15 \pmod {17}$, so are $(10+17)^2, (10+2\cdot 17)^2, \ldots$ – Ross Millikan Apr 30 '13 at 20:19