In this post we discuss automorphic numbers. Note that all numbers involved in this post are non negative integers.
Definition: Let have digits in its base representation. Then is said to be automorphic if .
In our base representation this means that the last digits of are precisely . In other words, the digits of are appended to . Note that since the digits of are appended to they are also appended to for any .
A list of some automorphic numbers can be found here. Our aim here is to characterize all such numbers in base .
Theorem: The automorphic numbers in base are given by .
Proof: Suppose is an automorphic number of digits. Then,
which is equivalent to
which is equivalent to the occurrence of exactly one of the following:
Now we consider all these cases one by one. Case 1 is equivalent to . Since had digits so this means . Similarly in case 2.
Now suppose case 3 holds. By the Chinese Remainder theorem there exists a unique solution to these two congruences modulo . We show that is a solution to them. By uniqueness it will then follow that case 3 is equivalent to saying that . Since has digits and has at most digits so we will therefore have equal to . Hence .
We first show that . Proceed by induction on . For note that .
Now assume the result for . Then and squaring yields and so thereby completing the induction step. Next observe that as so follows immediately, thereby completing case 3.
Note that our argument also implies that any number of the form is automorphic. Indeed, if had digits then we have shown that . Now as divides so , i.e. is automorphic.
To finish the proof we now consider case 4. We show that is a solution to the congruences of case 4. Clearly as . To show we proceed by induction as before. The base case may be explicitly worked out or be shown to hold by invoking Fermat’s theorem: , for any prime and integer . Next assume the result for , so that . Raising both sides to the fifth power yields the result for . The rest of the argument is similar.