Automorphic NumbersYou are currentlybrowsing as guest. Click here to log in 

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 "doublelength" 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~1a_n\pmod{2^{n+1}},$ and so $2^nr\equiv~a_n/5^n\pmod{5}$ and $5^nr\equiv~(1a_n)/2^n\pmod{2}.$ (Those righthand 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 $(1a_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
Last change to this page Full Page history Links to this page 
Edit this page (with sufficient authority) Change password 
Recent changes All pages Search 