Numbers that end in themselves when squared are known as automorphic numbers. Two examples are $25^2=625$ and $376^2=141376.$

Automorphic numbers always arise in pairs that sum to numbers of the form $10^n+1.$ The first five pairs (in some cases including numbers with leading zeroes) are:

1st 2nd sum
5 6 11
25 76 101
625 376 1001
0625 9376 10001
90625 09376 100001
890625 109376 1000001

The first number in each pair (call it $a_n$ ) is a multiple of $5^n$ and congruent to 1 modulo $2^n$ ; the second is a multiple of $2^n$ and congruent to 1 modulo $5^n$ . These numbers always exist and are unique modulo $10^n$ , by the Chinese remainder theorem.

You can find $a_n$ simply but inefficiently as follows. Start with $a_1=5.$ Then, for all n, $a_{n+1}$ is the last $n+1$ digits of ${a_n}^2.$ If you want to avoid having to deal with "double-length" numbers, here's one way to do it:

Suppose we know $a_n$ and want $a_{n+1}.$ Clearly $a_{n+1}=a_n+10^nr$ for some r; that is, $a_{n+1}$ differs from $a_n$ just by having some digit stuck on at the left. So, what's r ? Well, we have $10^nr\equiv~-a_n\pmod{5^{n+1}}$ and $10^nr\equiv~1-a_n\pmod{2^{n+1}},$ and so $2^nr\equiv~-a_n/5^n\pmod{5}$ and $5^nr\equiv~(1-a_n)/2^n\pmod{2}.$ (Those right-hand sides are guaranteed to be integers by the definition of $a_n.$ )

So if, as we construct the table above, we keep track of $a_n/5^n$ and $(1-a_n)/2^n$ as well as $a_n$ and $b_n,$ then all we need to know is the reciprocal of $2^n$ modulo 5 (this is a repeating sequence: 3,4,2,1,3,4,2,1,...) and the reciprocal of $5^n$ modulo 2 (this is always 1, of course). So, here's the final algorithm. Write $a_n=5^nc_n$ and $b_n=2^nd_n,$ and let $v_n$ be the repeating sequence of reciprocals. Then

Example: for $n=5$ we have a,b,c,d,v = 90625,9376,29,-2832,3; so r equals $-3.29\equiv-87\equiv3$ mod 5 and $-2832\equiv0$ mod 2; the only digit that works is 8.
Last change to this page
Full Page history
Links to this page
Edit this page
  (with sufficient authority)
Change password
Recent changes
All pages