Find the smallest integer $n > 0$ such that $2012$ divides $9^n-1$. Find the smallest integer $n > 0$ such that $2012$ divides $9^n-1$.

my thoughts:
$$2012=2 \cdot 2 \cdot 503$$
$503$ is prime. so by fermats little theorem $9^{502} \equiv 1$(mod $503$). again $9^n \equiv 1$ (mod $4$).
hence for $n=502$ equality holds but is it the smallest?
 A: $9^{502} \equiv1\mod503 \Longrightarrow$
$ 9^{502}-1\equiv0\mod503 \Longrightarrow $
$(9^{251}-1)(9^{251}+1)\equiv0\mod503 \Longrightarrow$
By fermat's theorem, $3^{502} \equiv1\mod503$
GCD $((9^{251}-1),(9^{251}+1))=2 \Longrightarrow$
$503\not\mid (9^{251}+1)$
Therefore, $9^{251}-1\equiv0\mod503$.
Smallest $n=251$. As $9^1 \neq 1 \mod 503$.
A: $503$ is a Sophie Germain prime, i.e. $\rm\: q = 503 = 2p\!+\!1 \:$ for prime $\rm\:p = 251,\:$ so order computation mod $\rm\,q\,$ is easy. We prove it generally (more insightful and just as easy). Yours is $\rm\: m=4,\ a= 9.$ 
Theorem $\ $ If $\rm\,\ p,\, q=2p\!+1\:$ are primes, and $\rm\ m\mid a\!-\!1,\,\ q\nmid a,a^2\!-\!1\:$ then 
$$\rm ord_{qm}(a)\ =\ p\ \ \ if\ \  a\ \  is\ a\ square\ mod\ q,\ \  else\ \ 2p$$
Proof $\ $ First, note that $\rm\:(q,m)=1\:$ (else $\rm\ q\mid m\mid a\!-\!1\mid a^2\!-\!1)\,\:$ contra hypothesis). Therefore 
$$\rm\:qm\mid a^n\!-\!1\iff q,m\mid a^n\!-\!1\iff q\mid a^n\!-\!1,\ \ \ since\ \ \ m\mid a\!-\!1\mid a^n\!-\!1.\:$$
So $\rm\: ord_{qm}(a) = ord_q(a) =: n.\,$ $\rm\,mod\ q\!:\ 1 \equiv a^{q-1}\! \equiv a^{2p},\:$ so $\rm\:n\mid 2p.\:$ By hypothesis $\rm\:q\nmid a^2\!-\!1,\:$ so $\rm\:n\nmid 2.\:$  If $\rm\:n = p\:$ then $\rm\:1 \equiv a^p \equiv a^{(p-1)/2},\:$  true iff $\rm\:a\:$ is a square $\rm\:mod\ q,\:$  by Euler's Criterion. 
A: Using Fermat's Little Theorem , $3^{502}\equiv1\pmod {503}$
$\implies (3^2)^{251}\equiv1\pmod {503}$
$\implies 9^{251}\equiv1\pmod {503}$
As we know, if $a^n\equiv 1\pmod n$ and $ord_na=d, d\mid n$ where integer $n>0$ (Proof)
If $ord_{503}9=d\implies d\mid 251$
As $251$ is prime, $d=1$ or $251$
As $9^1\not\equiv1\pmod {503} ,d=251$
