Since $2^{100} \equiv 1 \pmod {125}$ and $2^{100}$ is divisible by $8$, deduce that $2^{100} \equiv 376 \pmod {1000}$. In this book, "A Course In Algebra" the author Vinberg makes this deduction without any explanation and I was wondering if anyone could help me understand it:
Since $2^{100} \equiv 1 \pmod {125}$ and $2^{100}$ is divisible by $8$, we deduce that $2^{100} \equiv 376 \pmod {1000}$ i.e., that the decimal representation of $2^{100}$ ends with $376$.
Thanks.
 A: Without using the CRT (well, without explicitly using it) there are 8 numbers between 0 and 999 that are $1 \mod 125$: $1, 126, 251, 376, 501, 626, 751, 876$. It's easy to see that of these, the only one that is divisible by $8$ is $376$. Because the integers from $0$ to $999$ inclusive represent every congruency class $\mod 1000$, we must have that $2^{100} \equiv 376 \mod 1000$.
A: Well $1000=8\times 125$
Suppose $2^{100}=1000n+m$ where $0\le m \lt 1000$
If we take this equation modulo $125$ we get $1\equiv m$ so that $m=125p+1$
If we take the equation modulo $8$ we get $0\equiv m$ so that $m$ is a multiple of $8$
[Note how, because $8$ and $125$ are divisors of $1000$, the term in $n$ gets eliminated, isolating the term in $m$]
Now the Chinese Remainder Theorem guarantees a solution for $m$ here and tells you how to find one in the general case. But in this case it is just as easy to test $p=0,1,2,3 \dots$ and see which gives a value of $m$ which is a multiple of $8$.
So we get $1, 126, 251, 376, 501, 626, 751, 876$ as the possibles, and $376$ is the one we want.
Therefore $2^{100}=1000n+376$ and this gives you the final three decimal digits.
Once you understand what is going on here, you will find it quite easy to do similar problems. And you won't need to write down all the details to get there.
A: Using the Easy CRT formula for the Chinese Remainder solution we have
$$\begin{align}&x\equiv \color{#0a0}0\!\!\!\pmod{\!8}\\ &x\equiv \color{#c00}1\!\!\!\pmod{\!125}\\[.2em]
\iff\ &x\equiv \color{#c00}1\!+\!125\left[\dfrac{\color{#0a0}0\!-\!\color{#c00}1}{\!125}\!\bmod{8}\right]\equiv\, 1+125\,[\color{#90f}3]\equiv 376\end{align}\qquad\quad$$
using the fraction calculation  $\!\bmod 8\!:\ \dfrac{-1}{125}\equiv \dfrac{-1}{-3}\equiv \dfrac{1}{3}\equiv\dfrac{9}3\equiv\color{#90f}3$
Beware $ $ Modular fractions $\,a/b := ab^{-1}$ are well-defined only for fractions whose denominator $\,b\,$ is coprime to the modulus. See here for further discussion, and see here and here for many ways to calculate modular fractions and inverses.
