Get this Sum

Relevant wiki: Euler's Theorem

Let the sum be $S$ . We need to find $S \bmod 1000$ . By binomial theorem, we have $\displaystyle S \equiv \sum_{n=0}^{2018} \binom {2018}n \equiv 2^{2018} \text{ (mod 1000)}$ . Since $\gcd(2,1000) \ne 1$ , we have to consider the factors $2^3=8$ and $5^3 = 125$ of 1000 separately using Chinese remainder theorem.

Factor 8 : $S \equiv 2^{3028} \equiv 0 \text{ (mod 8)}$

Factor 125 :

$\begin{aligned} S & \equiv 2^{\color{#3D99F6}2018 \bmod \lambda(1000)} \text{ (mod 125)} & \small \color{#3D99F6} \text{Since }\gcd(2, 125) = 1 \text{, Euler's theorem applies.} \\ & \equiv 2^{\color{#3D99F6}2018 \bmod 100} \text{ (mod 125)} & \small \color{#3D99F6} \text{Carmichael lambda }\lambda (1000) = 100 \\ & \equiv 2^{18} \text{ (mod 125)} \\ & \equiv 2^{2\times 7+4} \text{ (mod 125)} \\ & \equiv (128^2)(16) \text{ (mod 125)} \\ & \equiv (3^2)(16) \text{ (mod 125)} \\ & \equiv 144 \text{ (mod 125)} \end{aligned}$

Since $144 \equiv 0 \text{ (mod 8)}$ , $S \equiv \boxed{144} \text{ (mod 1000)}$ .

30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742144