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.

  • $\begingroup$ I can't create rule to explain this. I have found two squares, which remainder on dividing by 17 is divisible by 3. It's 10 and 14, but i do not understand the next step. $\endgroup$ – Dan Sh Apr 29 '13 at 21:08
  • $\begingroup$ @DanSh: There are two others. $\endgroup$ – Ross Millikan Apr 29 '13 at 21:15
  • $\begingroup$ @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$ $\endgroup$ – Ross Millikan Apr 29 '13 at 21:18
  • $\begingroup$ 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. $\endgroup$ – Dan Sh Apr 30 '13 at 20:03
  • $\begingroup$ @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$ $\endgroup$ – Ross Millikan Apr 30 '13 at 20:19

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.