Infinite positive integer question 
Show that there are infinitely many positive integers $m$ for which
$$18^{m}+45^{m}+50^{m}+125^{m}$$
is divisible by $2006$

I am not sure of an approach to these type of divisibility problems when coming across in a book of contest questions, like the powers of $m$. What is a way to solve it?
 A: The second thread I linked did not show clearly how the quadratic residue applies to show that the exponent $29$ is not accidental. Here is an expansion of their idea:
We have $2006 = 2 \times 17 \times 59$ as the prime factorization.
For every $m$, $18^m + 45^m + 50^m + 125^m$ is even.
Taking mod $17$, the expression is equivalent to $1^m + (-6)^m + (-1)^m + 6^m$, which is zero for all odd $m$.
The hard part is taking mod $59$. It is equivalent to $$18^m + (-14)^m +(-9)^m + 7^m = (9^m + (-7)^m)(2^m+(-1)^m)$$
Hence we need to find odd $m$ such that $9^m \equiv 7^m \pmod {59}$.
We check that $7$ is a quadratic residue of $59$, either by quadratic reciprocity:
$$\left(\frac7{59}\right) = (-1)^{\frac{7-1}2\frac{59-1}2}\left(\frac{59}7\right)=-\left(\frac37\right)=1$$
since it is easy to check $3$ is not a quadratic residue mod $7$, or by observing
$$7 \equiv 59\times 6 + 7 = 361 = 19^2$$
Hence for some $a \in \mathbb Z$, we have $7^m \equiv a^{2m} \pmod {59}$.
By Fermat's Little Theorem, $a^{2m} \equiv 1 \pmod {59}$ when $m \equiv 29 \pmod {58}$.
Similarly, $9^m = 3^{2m} \equiv 1 \pmod {59}$ when $m \equiv 29 \pmod {58}$.
Hence $9^m \equiv 7^m \pmod {59}$ when $m \equiv 29 \pmod {58}$.
To conclude our findings, for every $m \equiv 29 \pmod {58}$, the expression is divisible by $2006$.
A: This Lemma solves the only nontrivial case: mod $\,p = 59\,$ (use reciprocity to check squareness).
Lemma $ $ Suppose $\,p=4j+3\,$ is prime and $\!\bmod p\!:\! \color{#0a0}{\,a,b\ \rm are\ nonsquares},\,$ $\color{#c00}{\,c,d\ \rm are\ squares}.\,$ Then there are infinitely many odd $\,m\in\Bbb N\,$ such that $\,p\mid a^m+b^m+c^m + d^m$.
Proof $\ $ Let $\, e = (p\!-\!1)/2 = 2j\!+\!1\,$ and let $\,k\in \Bbb N\,$ be odd, so $\,m := ek\,$ is odd.
Then by Euler's Criterion: $\!\bmod p\!:\ \,\color{#0a0}{a^e,b^e\equiv -1},\ \color{#c00}{c^e,d^e\equiv 1},\,$ thus
$$\begin{align} 
&\ \ \ \ \,a^m\ \ +\ \ b^m\  +\, \ c^m\  +\ d^m\\[.2em]
= &\ \ \  (\color{#0a0}{a^e})^k  + (\color{#0a0}{b^e})^k\! +\! (\color{#c00}{c^e})^k\! +\! (\color{#c00}{d^e})^k\\[.2em]
\equiv &\ \ (\color{#0a0}{-1})^k\! +\! (\color{#0a0}{-1})^k + \color{#c00}1^k + \color{#c00}1^k\\[.2em]
\equiv &\   \ \ \,{-}1\ \, +\ \, {-}1\ \ +\  1\ +\ 1\\[.2em] 
\equiv &\ \ \ \ 0
\end{align}\qquad\qquad$$
