Automorphic Numbers

Links to this page
Edit this page
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

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.
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout