# Automorphic Numbers AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

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

• $a_1=5,$ $b_1=6,$ $c_1=1,$ $d_1=-2.$
• Let r be the (unique) digit that's congruent mod 5 to $-v_nc_n$ and congruent mod 2 to $d_n.$ Then
• $a_{n+1}=a_n+10^nr;$ $b_{n+1}=10^{n+1}+1-a_n;$ $c_{n+1}=(c_n+2^nr)/5;$ $d_{n+1}=(d_n-5^nr)/2.$
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.