9999 problem!

Relevant wiki: Euler's Theorem

Since 7 and 1000 are coprime integers, we can use Euler's theorem and $\phi (1000) = 400$ . Let $x = 7^{9999}$ ; then we have:

$\begin{aligned} x & \equiv 7^{9999} \pmod{1000} \\ 7x & \equiv 7^{10000} \pmod{1000} \\ & \equiv 7^{10000 \mod 400} \pmod{1000} \\ \implies 7\color{#3D99F6}{x} & \equiv 1 \pmod{1000} \\ 7 \cdot \color{#3D99F6}{143} & \equiv 1001 \equiv 1 \pmod{1000} \\ \implies7^{9999} & \equiv x \equiv \boxed{143} \pmod{1000} \end{aligned}$

$7^{20} \equiv 1 \pmod{1000}$ $=> \space (7^{20})^{499} \equiv 1^{499} \pmod{1000}$ $=> \space 7^{9980} \equiv 1 \pmod{1000}$ $=> \space 7^{9980} \times 7^{19} \equiv 7^{19} \pmod{1000}$ $\boxed{=> \space 7^{9999} \equiv 7^{19} \pmod{1000}}$
$7^{2} \equiv 49 \pmod{1000}$ $=> \space 7^{4} \equiv 401 \pmod{1000}$ $=> \space 7^{8} \equiv 801 \pmod{1000}$ $=> \space 7^{16} \equiv 601 \pmod{1000}$ $=> \space 7^{19} \equiv 601\times343 \pmod{1000}$ $=>\boxed{\space 7^{19} \equiv 143 \pmod{1000}}$ $Therefore, \space \boxed{ \space 7^{9999} \equiv 143 \pmod{1000}}$

$\text{gcd}(\color{#D61F06}{7},\color{#D61F06}{1000})=1\implies 7^{\lambda(1000)}\equiv 1\pmod{1000}\implies \color{#3D99F6}{\boxed{7^{100}\equiv 1\pmod{1000}}}\\ \implies 7^{9999}\equiv 7^{99}\pmod{1000}\\ \text{Using Chinese remainder theorem this is equivalent to finding}\;\begin{cases} \color{#E81990}{7^{99}\pmod{8}}\\ \color{cyan}{7^{99}\pmod{125}}\end{cases}\\ 7^{99}\equiv (-1)^{99}\equiv \color{teal}{\boxed{-1}}\pmod{8}\\ \text{gcd}(\color{#20A900}{7},\color{#20A900}{125})=1\implies 7^{\lambda(125)}\equiv 1\pmod{125}\implies \color{teal}{\boxed{7^{100}\equiv 1\pmod{125}}}\\ \implies 7^{99}\equiv 7^{-1}\equiv \color{#EC7300}{\boxed{18}}\pmod{125}\\ \begin{cases} \color{grey}{7^{99}\equiv -1\pmod{8}}\\ \color{#624F41}{7^{99}\equiv 18\pmod{125}}\end{cases}\implies \color{#69047E}{7^{99}\equiv \boxed{\boxed{143}}\pmod{1000}}$