Skip to main content.

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) congruent to 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 congruent to 0 (mod 22)
n congruent to 1 (mod 52(1)

or

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

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

Similarly, from (2) we obtain n congruent to 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 congruent to ak (mod 10k.)
Suppose a2k = 10kn + ak is automorphic, so that (10kn + ak)2 congruent to 10kn + ak (mod 102k.)
We seek to express n in terms of ak.

Expanding, we obtain 2×10kak n + ak2 congruent to 10kn + ak (mod 102k.)
Simplifying, 10k(2ak − 1)n congruent to 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 congruent to (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 congruent to 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) congruent to 0 (mod 10k), we obtain
n congruent to (2ak − 1)(ak − ak2)/10k (mod 10k.)

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

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

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

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

Letting a2 = 25,  a4 congruent to (3×252 − 2×253) (mod 104) = 0625.
Then a8 congruent to (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.


Further reading

  1. Automorphic number

Source: Traditional

Back to top