The number 9376 has the property that the last four digits of 9376^2 are 9376, also know as 9376 being an automorphic number. How many four-digit numbers have this property? Are there values of n greater than 4 such that there is at least one n-digit number x that has this property? I know that there are no other automorphic numbers with 4 digits and there are automorphic numbers with more than 4 digits, but I need to prove this. Thanks!
[Math] Number theory question with automorphic numbers
elementary-number-theorynumber theory
Related Solutions
We can represent a number with non-decreasing digits by placing vertical bars in a string of nine ones. The number of ones to the left of the vertical bar represents the digit. For instance, $$| 1 1 1 | | 1 1 1 1 1 1 |$$ represents the number $0339$, while $$1 1 | 1 1 | 1 1 | 1 1 | 1$$ represents the number $2468$. Since a particular number is determined by which four of the thirteen symbols (four vertical bars and nine ones) are vertical bars, the number of non-decreasing numbers with four digits (including leading zeros) is $$\binom{13}{4} = \binom{13}{9}$$ as you found. To determine how many four-digit numbers (including those with leading zeros) are less than $5000$, we must subtract from these those non-decreasing four-digit numbers that are at least $5000$. Notice that in those non-decreasing four-digit numbers that are at least $5000$, the first vertical bar must be placed to the right of at least five ones. For instance, $$1 1 1 1 1 | | 1 | 1 | 1 1$$ represents the number $5567$. Since a particular non-decreasing four-digit number that is at least $5000$ is determined by which four of the last eight symbols (four vertical bars and four ones) are vertical bars, the number of non-decreasing four-digit numbers that are at least $5000$ is $$\binom{8}{4}$$ Hence, there are $$\binom{13}{4} - \binom{8}{4}$$ non-decreasing four-digit numbers, including those with leading zeros, that are less than $5000$.
Alternate Method: A non-decreasing number is completely characterized by the number of times each digit appears. Let $x_k$ represent the number of times the digit $k$ appears in the non-decreasing four-digit number, including those with leading zeros. Since there are four digits, $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 4$$ A particular number is determined by which nine of the thirteen symbols (nine addition signs and four ones) is an addition sign. For instance, $$1 + + + 1 1 + + + + + + 1$$ represents the number $0339$, while $$+ + 1 + + 1 + + 1 + + 1 +$$ represents the number $2468$. Thus, the total number of non-decreasing four-digit numbers is the number of ways nine addition signs can be placed in a row of four ones, which is $$\binom{4 + 9}{9} = \binom{13}{9}$$ From these, we subtract those non-decreasing four-digit numbers that are at least $5000$. The digits of non-decreasing four-digit numbers that are at least $5000$ satisfy the equation $$x_5 + x_6 + x_7 + x_8 + x_9 = 4$$ A particular number is determined by which four of the eight symbols (four addition signs and four ones) is an addition sign. Hence, there are $$\binom{4 + 4}{4} = \binom{8}{4}$$ non-decreasing four-digit numbers that are at least $5000$. Hence, the number of non-decreasing four-digit numbers that are less than $5000$, including those with leading zeros, is $$\binom{13}{9} - \binom{8}{4}$$
Those numbers are called Automorphic numbers (as you just said). There is a longer list here:
https://oeis.org/A007185 is $5^{2^n}$ $\mod 10^n$
https://oeis.org/A016090 is $16^{5^n}$ $\mod 10^n$
There are also other sequences like these for any $a$, coprime to $10$, the Automarphic sequence is $a^{10^n}$ $=$ 1 $\mod 10^n$, and if $a$ $=$ $10x$, then $a^n$ $=$ 0 $\mod 10^n$.
$n^3$, any string of digits ending in 1, 3, 7, 9 can be the ending digits of a perfect cube, for other strings, the last three digits are a multiple of 8, 125 or just 000 (for numbers $n$ divisible by 10)
If $x$ is coprime to 10, then there is an integer $a$ such that:
$a^a$ $=$ $x$ $\mod 10^n$, so it is easy to see that the last digit of $a^a$ is either 0, 1, 3, 4, 5, 6, 7, 9.
Best Answer
You can just directly prove this. Suppose $n$ is $4$-digit automorphic. Then $n^2 - n \equiv 0 \bmod 10000$. Let's decompose this into the two prime power equations:
$$n^2 - n \equiv 0 \bmod 16$$
$$n^2 - n \equiv 0 \bmod 625$$
As $n^2 - n = n(n-1)$, and as $n$ is relatively prime to $n-1$, we must have that $n \equiv 0 \bmod 2^4$ and $n \equiv 1 \bmod 5^4$, or $n \equiv 1 \bmod 2^4$ and $n \equiv 0 \bmod 5^4$ (if $n$ is equivalent to $0$ mod both, then $n$ is $0$).
I will work with the first set of conditions. So $n \equiv 1 \bmod 625$ means that $n = 1 + 625k$ for some $k$. But then $n = 1 + 625k \equiv 1 + k \bmod 16$, so that $k \equiv 15 \bmod 16$.
Putting these together, $n = 1 + 625(15 + 16l) = 9376 + 10000l$ for some $l$. So if $n$ is 4 digits and satisfies this set of conditions, then $n = 9376$. I'll leave the other case to you.
For more digits, you might just check that $109376$ is also automorphic. This is quickly proved with the same technique above. You might notice that we didn't actually assume the number of digits of $n$ anywhere - so there are only two sets of final digits an automorphic number might have. One happens to end in $9376$ as shown here.