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 12² = 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 x² 444 (mod 1000.) We will solve the congruence modulo 2³ and modulo 5³, and then put the solutions together using the Chinese Remainder Theorem.
We have x² 4 (mod 8) and x² 69 (mod 125.)

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

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

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

Set x = 5t ± 2, for some integer t, so that (5t ± 2)² = 25t² ± 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)² = 625t² ± 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, x² = 250000s² ± 38000s + 1444 444 (mod 1000.).

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

Solution to puzzle 89: Square digits

Find an upper bound for length

Solve for length 3

Further reading