# Solution to puzzle 89: Square digits

A perfect square has length n if its last n (decimal) digits are the same and non-zero.  What is the maximum possible length?  Find all squares that achieve this length.

## Find an upper bound for length

The last decimal digit of a perfect square must be 0, 1, 4, 9, 6, or 5.
A positive integer ending in 11, 44, 99, 66, 55, is congruent, respectively, to 3, 0, 3, 2, 3 (modulo 4.)
Since all squares are congruent to 0 or 1 (mod 4), any square with length greater than 1 must end in 44.
An example is 122 = 144.

A square of length 4 would be congruent to 4444 (mod 10000), and therefore congruent to 12 (mod 16.)
However, this is impossible, as all squares are congruent to 0, 1, 4, or 9 (mod 16.)
(Alternatively, consider 12 + 16t = 4(3 + 4t), for some integer t.  If 12 + 16t is a square, then 3 + 4t is a square.  However, all squares are congruent to 0 or 1 (mod 4.))

We have therefore established that the length of a perfect square cannot exceed 3.  If a square of length 3 exists, it must end in 444.

## Solve for length 3

Consider now x2 444 (mod 1000.)  We will solve the congruence modulo 23 and modulo 53, and then put the solutions together using the Chinese Remainder Theorem.
We have x2 4 (mod 8) and x2 69 (mod 125.)

By inspection, x2 4 (mod 8) x 2 (mod 4.)

We will solve x2 69 (mod 125) by first considering the equation, modulo 5.  We will then use the solution to this congruence to solve modulo 52, and then modulo 53.

x2 69 (mod 125) x2 4 (mod 5), and x2 19 (mod 25.)
By inspection, x2 4 (mod 5) x ±2 (mod 5.)

Set x = 5t ± 2, for some integer t, so that (5t ± 2)2 = 25t2 ± 20t + 4 19 (mod 25.)
Hence ±20t 15 (mod 25), from which 4t ±3 (mod 5), and then t ±2 (mod 5), x  ±12 (mod 25.)

Set x = 25t ± 12, for some integer t, so that (25t ± 12)2 = 625t2 ± 600t + 144 69 (mod 125.)
Hence ±100t 50 (mod 125), from which 2t ±1 (mod 5), and then t ±3 (mod 5), x  ±87 (mod 125); or, equivalently, x  ±38 (mod 125.)

By the Chinese Remainder Theorem, since 4 and 125 are relatively prime, there is one solution (modulo 4 × 125) for each pair of solutions, modulo 4 and 125.  Hence, in this case, there are two solutions, modulo 500.

We have x = 125t ± 38, for some integer t.  Recall that x 2 (mod 4.)
Hence 125t ± 38 2 (mod 4) t 0 (mod 4.)
Setting t = 4s, for some integer s, we therefore obtain x = 500s ± 38.
Then, x2 = 250000s2 ± 38000s + 1444 444 (mod 1000.).

We conclude that the maximum possible length is 3, in which case the square must end in 444.  Moreover, x2 ends in 444 if, and only if, x ±38 (mod 500.)