Find the last three digits of $19^{100}$

Question

Find the last three digits of $19^{100}$

---

$19^{100}=361^{50}=(1+360)^{50}=\binom{50}{0}+\binom{50}{1}360+\binom{50}{2}360^2+\cdots$
When we divide it by $1000$, the remainder comes out to be $001$, so the last three digits must be $001$, but in my book, the answer is given as $801$. I dont know where I am wrong. Please help.

Answer 1

Your argument is correct (assuming that, as someone commented, that you meant $19$ instead of $99$), and so is your answer.

Answer 2

(This answer addresses the question in the original title, but my comment above shows that they give the same answer.)

Hint: $$(100-1)^{100} \equiv \sum_{k=0}^{100} \binom{100}{k} (-1)^{100-k} 100^k \equiv \underbrace{-\binom{100}{1} 100}_{\equiv 0 \pmod{1000}} + 1 \equiv 1 \pmod{1000}$$

---

As the alternative answer points out, your argument is correct, but there's a simpler and more straightforward answer by considering the binominal expansion of $(100-1)^{100}$. Since you only want the last three digits, only the terms $100^k$ with $k = 0,1$ remains.

This approach is much simpler than

1. justifying $99^{100} \equiv 19^{100} \pmod{1000}$
2. reducing the exponent $99^{100}$ to $361^{50}$
3. considering the binomial expansion of $(360+1)^{50}$, whose coefficients $\binom{50}{k}$ gives less trailing zeros. (i.e. more terms needed $\implies$ slower calculations)

Answer 3

The power-factors of 1000 are 8 and 125. If n is coprime to 1000, then the period of any x/1000, is a sum of some $x_1/8$ and some $x_2/125$.

The eights are periodic over two places, the 125 is periodic over 100 places. So any co-prime number, raised to the 100 power, will leave a remainder of 1, since we have shown that $1000 \mid x^{100} - 1$, and thus $x^{100} = 1 \pmod{1000}$.

Answer 4

Alternatively: $$19^{100}=(20-1)^{100}=\underbrace{20^{100}-100\cdot 20^{99}+\cdots -\begin{pmatrix} 100\\ 3\end{pmatrix}\cdot 20^3}_{=1000A}+\begin{pmatrix} 100\\ 2\end{pmatrix}\cdot 20^2-\begin{pmatrix} 100 \\ 1\end{pmatrix}\cdot 20+\begin{pmatrix} 100 \\ 0\end{pmatrix}=$$ $$1000A+1978000+1.$$ Hence: $$19^{100} \equiv 1 \pmod{1000}.$$