How to find all positive integers whose square ends in $444$?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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