# Solution to puzzle 94: Square endings

Find all 8-digit natural numbers n such that n2 ends in the same 8 digits as n.  Numbers are written in standard decimal notation, with no leading zeroes.

Numbers with this property are called automorphic.

## Find 2-digit automorphic numbers

We begin by finding all 2-digit automorphic numbers: consider n2 − n = n(n − 1) 0 (mod 100).
Since n is a 2-digit number, neither n nor n − 1 is divisible by 100.
Therefore, since n and n − 1 are relatively prime, one or both of the following must hold:

n 0 (mod 22)
n 1 (mod 52(1)

or

n 1 (mod 22)
n 0 (mod 52(2)

From (1), we have n = 1 + 25r, for some integer r, and so 1 + 25r 1 + r 0 (mod 4.)
Hence r 3 (mod 4), and n = 1 + 25(3 + 4s) = 76 + 100s, for some integer s.
Therefore n 76 (mod 100.)

Similarly, from (2) we obtain n 25 (mod 100.)

Note that for k-digit automorphic numbers, where k > 1, equations (1) and (2) hold modulo 2k and modulo 5k.  The Chinese Remainder Theorem guarantees that each set of equations has a unique solution, modulo 10k.  Hence there is always precisely one automorphic number ending in 5, and one ending in 6, subject to the caveat that each number may have one or more leading zeroes.

## Establish a recurrence relation

We could apply the above method directly to 8-digit numbers.  However, we know that an 8-digit automorphic number must end in 76 or 25.  Can we make use of this fact algebraically?

For k > 0, let ak be an automorphic number with k digits.  That is, ak2 ak (mod 10k.)
Suppose a2k = 10kn + ak is automorphic, so that (10kn + ak)2 10kn + ak (mod 102k.)
We seek to express n in terms of ak.

Expanding, we obtain 2×10kak n + ak2 10kn + ak (mod 102k.)
Simplifying, 10k(2ak − 1)n ak − ak2 (mod 102k.)
As both sides of this equation, and the modulus itself, are divisible by 10k, we may divide by that quantity, obtaining
(2ak − 1)n (ak − ak2)/10k (mod 10k(3)

Now note that 2ak − 1 is relatively prime with 10k.
(This follows because 2ak − 1 is odd, and, since ak 0 or 1 (mod 5), 2ak − 1 is not divisible by 5.)
Hence (3) has precisely one solution for n.

Now multiply (3) by 2ak − 1.
Noting that 4(ak2 − ak) 0 (mod 10k), we obtain
n (2ak − 1)(ak − ak2)/10k (mod 10k.)

This gives us the following recurrence relation:
a2k ak + 10k[(2ak − 1)(ak − ak2)/10k (mod 10k)]

Since s × [r (mod s)] sr (mod s2), this simplifies to

 a2k ak + (2ak − 1)(ak − ak2) (mod 102k) ak + (3ak2 − 2ak3 − ak) (mod 102k) (3ak2 − 2ak3) (mod 102k), since ak < 102k

Letting a2 = 76,  a4 (3×762 − 2×763) (mod 104) = 9376.
Then a8 (3×93762 − 2×93763) (mod 108) = 87109376.

Letting a2 = 25,  a4 (3×252 − 2×253) (mod 104) = 0625.
Then a8 (3×6252 − 2×6253) (mod 108) = 12890625.

Hence, the only 8-digit natural numbers n such that n2 ends in the same 8 digits as n, are 12890625 and 87109376.