Find all 8-digit natural numbers n such that n^{2} 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*.

We begin by finding all 2-digit automorphic numbers: consider n^{2} − 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 2^{2})

n 1 (mod 5^{2}) (1)

or

n 1 (mod 2^{2})

n 0 (mod 5^{2}) (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 2^{k} and modulo 5^{k}. The Chinese Remainder Theorem guarantees that each set of equations has a unique solution, modulo 10^{k}. 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.

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 a_{k} be an automorphic number with k digits. That is, a_{k}^{2} a_{k} (mod 10^{k}.)

Suppose a_{2k} = 10^{k}n + a_{k} is automorphic, so that (10^{k}n + a_{k})^{2} 10^{k}n + a_{k} (mod 10^{2k}.)

We seek to express n in terms of a_{k}.

Expanding, we obtain 2×10^{k}a_{k }n + a_{k}^{2} 10^{k}n + a_{k} (mod 10^{2k}.)

Simplifying, 10^{k}(2a_{k} − 1)n a_{k} − a_{k}^{2} (mod 10^{2k}.)

As both sides of this equation, and the modulus itself, are divisible by 10^{k}, we may divide by that quantity, obtaining

(2a_{k} − 1)n (a_{k} − a_{k}^{2})/10^{k} (mod 10^{k}) (3)

Now note that 2a_{k} − 1 is relatively prime with 10^{k}.

(This follows because 2a_{k} − 1 is odd, and, since a_{k} 0 or 1 (mod 5), 2a_{k} − 1 is not divisible by 5.)

Hence (3) has precisely one solution for n.

Now multiply (3) by 2a_{k} − 1.

Noting that 4(a_{k}^{2} − a_{k}) 0 (mod 10^{k}), we obtain

n (2a_{k} − 1)(a_{k} − a_{k}^{2})/10^{k} (mod 10^{k}.)

This gives us the following recurrence relation:

a_{2k} a_{k} + 10^{k}[(2a_{k} − 1)(a_{k} − a_{k}^{2})/10^{k} (mod 10^{k})]

Since s × [r (mod s)] sr (mod s^{2}), this simplifies to

a_{2k} | a_{k} + (2a_{k} − 1)(a_{k} − a_{k}^{2}) (mod 10^{2k}) |

a_{k} + (3a_{k}^{2} − 2a_{k}^{3} − a_{k}) (mod 10^{2k}) | |

(3a_{k}^{2} − 2a_{k}^{3}) (mod 10^{2k}), since a_{k} < 10^{2k} |

Letting a_{2} = 76, a_{4} (3×76^{2} − 2×76^{3}) (mod 10^{4}) = 9376.

Then a_{8} (3×9376^{2} − 2×9376^{3}) (mod 10^{8}) = 87109376.

Letting a_{2} = 25, a_{4} (3×25^{2} − 2×25^{3}) (mod 10^{4}) = 0625.

Then a_{8} (3×625^{2} − 2×625^{3}) (mod 10^{8}) = 12890625.

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

Source: Traditional