Automorphic Numbers

In this post we discuss automorphic numbers. Note that all numbers involved in this post are non negative integers.

Definition: Let $x$ have $n$ digits in its base $10$ representation. Then $x$ is said to be automorphic if $x^2\equiv x\pmod {10^n}$.

In our base $10$ representation this means that the last $n$ digits of $x^2$ are precisely $x$. In other words, the digits of $x$ are appended to $x^2$. Note that since the digits of $x$ are appended to $x^2$ they are also appended to $x^m$ for any $m\ge 1$.

A list of some automorphic numbers can be found here. Our aim here is to characterize all such numbers in base $10$.

Theorem: The automorphic numbers in base $10$ are given by $\{0,1\}\cup\{5^{2^m}\pmod {10^m}:m\ge 1\}\cup\{16^{5^m}\pmod {10^m}:m\ge 1\}$.

Proof: Suppose $x$ is an automorphic number of $n$ digits. Then,

$x(x-1)\equiv 0\pmod {10^n}$

which is equivalent to

$\Big(x\equiv 0\text{ or }1\pmod{2^n}\Big) \text{ and } \Big(x\equiv 0\text{ or }1\pmod{5^n}\Big)$

which is equivalent to the occurrence of exactly one of the following:

Case 1: $x\equiv 0\pmod {2^n} \text{ and } x\equiv 0\pmod {5^n}$

Case 2: $x\equiv 1\pmod {2^n} \text{ and } x\equiv 1\pmod {5^n}$

Case 3: $x\equiv 1\pmod {2^n} \text{ and } x\equiv 0\pmod {5^n}$

Case 4: $x\equiv 0\pmod {2^n} \text{ and } x\equiv 1\pmod {5^n}$

Now we consider all these cases one by one. Case 1 is equivalent to $x\equiv 0\pmod {10^n}$. Since $x$ had $n$ digits so this means $x=0$. Similarly $x=1$ in case 2.

Now suppose case 3 holds. By the Chinese Remainder theorem there exists a unique solution to these two congruences modulo $10^n$. We show that $5^{2^n}$ is a solution to them. By uniqueness it will then follow that case 3 is equivalent to saying that $x\equiv 5^{2^n}\pmod {10^n}$. Since $x$ has $n$ digits and $5^{2^n}\pmod {10^n}$ has at most $n$ digits so we will therefore have $x$ equal to $5^{2^n}\pmod {10^n}$. Hence $x\in\{5^{2^m}\pmod {10^m}:m\ge 1\}$.

We first show that $5^{2^n}\equiv 1\pmod {2^n}$. Proceed by induction on $n$. For $n=1$ note that $5^{2}\equiv 1\pmod 2$.

Now assume the result for $k$. Then $5^{2^k}=q2^k+1$ and squaring yields $5^{2^{k+1}}=q^2 2^{2k}+q2^{k+1}+1=(q^2 2^{k-1}+q)2^{k+1}+1$ and so $5^{2^{k+1}}\equiv 1\pmod {2^{k+1}}$ thereby completing the induction step. Next observe that as $n<2^n$ so $5^{2^n}\equiv 0\pmod {5^n}$ follows immediately, thereby completing case 3.

Note that our argument also implies that any number of the form $5^{2^m}\pmod{10^m}$ is automorphic. Indeed, if $a=5^{2^m}\pmod{10^m}$ had $t\le m$ digits then we have shown that $a^2\equiv a\pmod {10^m}$. Now as $10^t$ divides $10^m$ so $a^2\equiv a\pmod {10^t}$, i.e. $a$ is automorphic.

To finish the proof we now consider case 4. We show that $16^{5^n}$ is a solution to the congruences of case 4. Clearly $16^{5^n}\equiv 0\pmod {2^n}$ as $n<4.5^n$. To show $16^{5^n}\equiv 1\pmod {5^n}$ we proceed by induction as before. The base case may be explicitly worked out or be shown to hold by invoking Fermat’s theorem: $m^p\equiv m\pmod p$, for any prime $p$ and integer $m$. Next assume the result for $k$, so that $16^{5^k}=q5^k+1$. Raising both sides to the fifth power yields the result for $k+1$. The rest of the argument is similar.$\Box$