Solution to puzzle 94: Square endings

Find all 8-digit natural numbers n such that n² 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 n² − 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²)
n 1 (mod 5²)  (1)

or

n 1 (mod 2²)
n 0 (mod 5²)  (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.

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 a_k be an automorphic number with k digits.  That is, a_k² a_k (mod 10^k.)
Suppose a_2k = 10^kn + a_k is automorphic, so that (10^kn + a_k)² 10^kn + a_k (mod 10^2k.)
We seek to express n in terms of a_k.

Expanding, we obtain 2×10^ka_k n + a_k² 10^kn + a_k (mod 10^2k.)
Simplifying, 10^k(2a_k − 1)n a_k − a_k² (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²)/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² − a_k) 0 (mod 10^k), we obtain
n (2a_k − 1)(a_k − a_k²)/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²)/10^k (mod 10^k)]

Since s × [r (mod s)] sr (mod s²), 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 a₂ = 76,  a₄ (3×76² − 2×76³) (mod 10⁴) = 9376.
Then a₈ (3×9376² − 2×9376³) (mod 10⁸) = 87109376.

Letting a₂ = 25,  a₄ (3×25² − 2×25³) (mod 10⁴) = 0625.
Then a₈ (3×625² − 2×625³) (mod 10⁸) = 12890625.

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

---

Further reading

1. Automorphic number

Source: Traditional

Back to top