Divisibility of large number This was a question asked in a competitive exam:

$(300^{3000} -1 )$ is divisible by
a) $401$ b) $501$ c) $301$ d) $901$

The answer is $301$. Not sure how they arrived at the answer. Can somebody explain ?

An alternative to Dan's answer: 
$300 \equiv -1 \pmod{301}$, and $(-1)^{5 \cdot k} \equiv -1 \pmod{301}$. Now 
$$
300^{3000} - 1 = (300^{1500}+1)(300^{1500}-1)=(300^{1500}+1)(300^{750}+1)(300^{375}+1)(300^{375}-1),
$$
so 
$$
(300^{375}+1) \equiv  (300^{5\cdot 75}+1) \equiv 0 \bmod 301
$$
