I was solving a problem which asks to find the remainder,
$$\text{When}~~: \sum_{r=0}^{1008}{2016 \choose2r}{3^{2016-2r}8^r} ~~~\text{is divided by $2017$} $$
Original form:$~~\dfrac{1}{2}\{(3+2\sqrt{2})^{2016}+(3-2\sqrt{2})^{2016}\}$
Please tell me how to solve this kind of problems and specifically this one.
From my comment: for an odd prime $p$, $\binom{p-1}{k} \equiv (-1)^k$ (mod $p$) for $0 \leq k \leq p-1$, since $$k! = (-1)^k (-1)(-2) \cdots (-k) \equiv (-1)^k (p-1)(p-2) \cdots (p-k) = (-1)^k \frac{(p-1)!}{(p-1-k)!} \quad (\mbox{mod } p).$$ Thus since 2017 is prime the sum simplifies to $$\sum_{r=0}^{1008} (-1)^{2r} 3^{2016 - 2r} 8^r = \sum_{r=0}^{1008} 9^{1008 - r} 8^r = 9^{1009} - 8^{1009}.$$ Fermat's little theorem is the standard way to manipulate large powers mod $p$ (or mod general $n$) -- it says that $a^{p-1} \equiv 1$ (mod $p$) for $a$ not divisible by $p$, or more generally, that $a^{\varphi(n)} \equiv 1$ (mod $n$) when $a$ is relatively prime to $n$, where $\varphi$ is Euler's totient function.
1009 isn't a large enough exponent to use Fermat's little theorem to reduce this, but it will work if we can find square roots of 8 and 9 mod 2017. Note $9 = 3^2$, and $8 \equiv 2025 = 45^2$ (mod 2017), so by Fermat's little theorem, $9^{1008} = 3^{2016} \equiv 1$ (mod 2017) and $8^{1008} \equiv 45^{2016} \equiv 1$ (mod 2017), so our remainder is $9^{1009} - 8^{1009} \equiv 9 - 8 = 1$.