Computation of residue class of $2^{100}$ modulo $1000$

Question

$2^{100} \equiv 1 \ (\text{mod}\ 125)$ and is divisible by $8$. Why then is $2^{100} \equiv 376 \ (\text{mod}\ 1000)$?

Answer 1

We have:

If ($a\equiv b \mod{c}$) & ($ a\equiv b \mod{d}$) & ($c$ and $d$ are coprime), then $a\equiv b \mod{dc}$

As $8= 2^3$ and $125=5^3$ are coprime, and $8*125=1000$, then to find $2^{100} \mod{1000}$, it is enough to find the smallest $b$ such that $2^{100}\equiv b \mod{125}$ and $2^{100}\equiv b \mod{8}$. We have $2^{100}\equiv 0 \mod{8}$, and $2^{100}\equiv 1 \mod{125}$, moreover
$$2^{100}\equiv 1\equiv 126\equiv 251\equiv 376\equiv 501 \equiv 626\equiv 751\equiv 876 \mod{125}$$ and
$$2^{100}\equiv 0\equiv 8 \equiv 120 \equiv 248\equiv 376 \mod{8}$$

Thus our $b$ is equal to $376$.

Answer 2

In the list of all numbers congruent to $1$ modulo $125$ and less than $1000$: $$1,\ 126,\ 251,\ 376,\ 501,\ 626,\ 751,\ 876,$$ only $376$ is a multiple of $8$.

Answer 3

$1000 = 2^3 \times 5^3 = 8 \times 125$

$2^{100} \equiv 8 \times 2^{97} \equiv 0 \pmod 8$

$\varphi(125)=5^3 - 5^2 = 100$,
so $2^{100} \equiv 1 \pmod{125}$

We need to find $x$ such that $x \equiv 0 \pmod 8$ and $x \equiv 1 \pmod{125}$.

$x \equiv 0 \pmod 8 \implies x = 8y$ for some integer $y$.
$x \equiv 1 \pmod{125} \implies 8y \equiv 1 \pmod{125}$

    | 125   1     0  {125 =  (1)125 +   (0)8}
-15 |   8   0     1  {  8 =  (0)125 +   (1)8}
 -2 |   5   1   -15  {  5 =  (1)125 + (-15)8}
  2 |  -2  -2    31  { -2 = (-2)125 +  (31)8}
    |   1  -3    47  {  1 = (-3)125 +  (47)8}

$8y \equiv 1 \pmod{125} \implies y \equiv 47 \pmod{125} \implies x \equiv 376 \pmod{1000}$