The question is from the $1995$ British Mathematical Olympiad.
I’ve figured out that $38^2$ ends with a $444$. So $N^2 \equiv 38^2 \pmod{ 1000}$. Consequentially $N^2 – 38^2 \equiv 0 \pmod{ 1000}$. Using difference of two squares we see that $(N-38)(N+38) \equiv 0 \pmod{ 1000}.$
Now I’m stuck. I’m not too sure if factoring was the right way to go. Also feel free to post any other solutions that begin with with a different route.
Best Answer
This is solving $$x^2\equiv444\pmod{1000}.$$ By the Chinese remainder theorem, this is equivalent to the two congruences $$x^2\equiv444\equiv4\pmod{8}$$ and $$x^2\equiv444\equiv69\pmod{125}.$$ The solution of the first is $x\equiv2\pmod4$ and that of the second is $x\equiv\pm38\pmod{125}$. Putting these together using CRT gives $x\equiv\pm38\pmod{500}$. This means that $x$ ends in $038$ or $462$ or $538$ or $962$.