How to find all positive integers whose square ends in $444$? 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.
 A: 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$.
A: $$n^2\equiv444\pmod{1000}\equiv38^2$$
$$\implies n^2\equiv38^2\pmod8\equiv4$$
$\implies8\mid(n+2)(n-2)$
As $n$ is even,
$\implies2\mid\dfrac{n+2}2\cdot\dfrac{n-2}2$
In either case
$$n\equiv2\pmod4\ \ \ \ (1)$$
and $n^2\equiv38^2\pmod{125}\implies n\equiv\pm38\pmod{125}\ \ \ \ (2)$
as $125=5^3$ has primitive roots, $m^2\equiv1\pmod{5^3}$ will have exactly two in-congruent roots. 
Now apply  Chinese Remainder Theorem
A: $$N^2\equiv444\pmod{1000}\implies N^2\equiv4\pmod{10}$$
$\implies N=10m\pm2$
$N^2=(10m\pm2)^2=4\pm40m+100m^2\equiv4\pm40m\pmod{100}$
We need $4\pm40m\equiv44\pmod{100}$
$4+40m\equiv44\pmod{100}\implies40m\equiv40\pmod{100}\iff100|40(m-1)\iff5|2(m-1)$
$m=5r+1$(say)
$N=10(5r+1)+2=50r+12$
$N^2=(50r+12)^2=2500r^2+1200r+144\equiv444\pmod{1000}$
$2500r^2+1200r\equiv300\pmod{1000}$
$\iff25r^2+12r\equiv3\pmod{10}$
$\iff5r^2+2r\equiv3\pmod{10}$
Clearly, $r$ can not be even $r=2t+1$(say)
$5r^2+2r-3=5(2t+1)^2+2(2t+1)-3\equiv4t+4\pmod{10}\iff5|2(t+2)\implies5|(t+2)$
$t+2=5s$(say)
$r=2(5s-2)+1=10s-3$
$N=50(10s-3)+12=500s-138,0\le500s-138<1000\implies1\le s\le2$
Similarly for $N=10m-2$ which can also be derived from $N=10m+2$
as for $a$ is a solution, so will be $1000-a$
A: Starting with your last line, if $1000|(N-38)(N+38)$, then $N$ can not be odd, and if it is even, then it can not be a multiple of $4$, thus $N=4M+2$ and
$$
125|2(M-9)(M+10).
$$
The factors $(M-9)$ and $(M+10)$ can not be divisible by $5$ at the same time, so either 


*

*$M=125K+9$, $N=500K+38$ or

*$M=125K-10$, $N=500K-38$.

