1
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why does n^2 - n equal 0mod(16) or 625? Doesn't 0 mod(n) always equal 0? $\endgroup$ – user128914 Feb 27 '14 at 3:49
  • $\begingroup$ Where do you see $0 = 0$ somewhere? I'm referring to the Chinese remainder theorem to decompose. $\endgroup$ – davidlowryduda Feb 27 '14 at 3:51
  • $\begingroup$ 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. $\endgroup$ – user128914 Feb 27 '14 at 3:53
  • $\begingroup$ 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" $\endgroup$ – davidlowryduda Feb 27 '14 at 3:57
  • $\begingroup$ Got it. Thanks so much! $\endgroup$ – user128914 Feb 27 '14 at 3:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.