Q:

Find the smallest $4$ digit number which is a factor of $2005^6 - 1$.

Find the smallest $4$ digit number which is a factor of $2005^6 - 1$.
My attempt:
We see that $(2005-1)$ is a factor of $2005^6-1$ by the factorization of $2005^6-1$. Therefore, $1002$ is a factor of $2005^6-1$. I then have to show that $1001$ is not a factor but how do I do that? Should I use the factorization of $x^6-1$?

A:

$2005^6-1\equiv 3^6-1\not \equiv 0 \pmod {1001}$. Further, as mentioned in comments by Steven, you need to eliminate $1000$ as a factor too. 

