Showing that, if $n,10$ are coprime, then the last $3$ digits of $n^{101}$ will be the same as $n$'s.

Question

Let $n$ be a positive integer where $n$ and $10$ are coprime number. Prove that then the last 3 digits of $n^\text{101}$ will be equal to the last 3 digits of $n$.

SOURCE: Bangladesh Math Olympiad

I basically know how to find the last digit of a base with a large exponent. Whatever the exponent in the event of one digit such as $1, 5, 6$ and $9$ will be, the last digit of the number will always result in that specific number which we have used.

So, the last 3 digit of $n$ can be constructed in $^4P_3$ ways with having that 4 digits $1, 5, 6$ and $9$ respectively. But how to determine only that distince value of $n$ and justify that the number and $10$ are coprime number>

The instruction of any kind of reference or any good books related with decimal expansion or number theory will be very helpful for me in the case of a beginner and some basic conception because there is no availability of satisfactory books written on number theory in our country which I have read some. Thanks in advance.

Answer 1

We need to prove that $n^{101}-n$ is divisible by $1000,$ for which it's enough to prove that $$n^{100}\equiv1\pmod{1000}.$$ Now, since $n^5\equiv n(\mod5),$ we obtain $n^4\equiv1\pmod5$ which gives $$n^{100}-1=(n^4-1)(n^{96}+n^{92}+...+1)=(n^4-1)(\left(n^4\right)^{24}+\left(n^4\right)^{23}+...+1)\equiv0\pmod{125}$$ and since $n$ is an odd number, we obtain: $$n^{100}-1=(n^{50}-1)(n^{50}+1)=(n^{25}-1)(n^{25}+1)(n^{50}+1)\equiv0\pmod8$$ and we are done!

Answer 2

This is a group theory question, not a number theory question. You want to show that any element of the multiplicative group $(\Bbb Z/1000)^*$ has order dividing $100$.

It's fairly easy to see that the order of this group is $400$. Also, both $501$ and $999$ have order $2$ in this group (and therefore $499$ also has order $2$). Any finite abelian group is a direct product of cyclic groups, so if we can find one more element of order $2$, we'll know that every cyclic component must have order dividing $100$ and we'll be done. (Based on what we know so far, it's possible that the group is $\Bbb Z / 2 \times \Bbb Z / 200$.) We also find that $251$ (and therefore $749$) has order $2$ in the group and we are done.