# Number theory question with automorphic numbers

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!

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.

• Why does n^2 - n equal 0mod(16) or 625? Doesn't 0 mod(n) always equal 0? – user128914 Feb 27 '14 at 3:49
• Where do you see $0 = 0$ somewhere? I'm referring to the Chinese remainder theorem to decompose. – davidlowryduda Feb 27 '14 at 3:51
• Sorry, not the most knowledgable about number theory. I was talking about the line n^2 − n ≡ 0mod16 because I was under the belief that 0 mod(x) is always equal to 0, so we would get n^2 - n ≡ 0. – user128914 Feb 27 '14 at 3:53
• How about this. Anytime I wrote $a \equiv b \bmod x$, you should read it as "$x$ divides $a - b$." Since $10000$ divides $n^2 - n$, then we have both $16$ and $25$ divides $n^2 - n$. As $n^2 - n = n(n-1)$, we must have that $16$ divides one of $n$ and $n-1$,... and so on. This will make the answer understandable without seeing the potentially confusing word "mod" – davidlowryduda Feb 27 '14 at 3:57
• Got it. Thanks so much! – user128914 Feb 27 '14 at 3:57