# 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?

-
$9^n-1=8(9^{n-1}+9^{n-2}+....+1)$ The second term$((9^{n-1}+9^{n-2}+....+1))$ has to be a multiple of $503$. –  Inceptio Mar 15 '13 at 10:36
The smallest could be a divisor of 502. Actually, it's 251. –  Jean-Claude Arbaut Mar 15 '13 at 10:37
@arbautjc: And that proves it. $251$ is a prime. –  Inceptio Mar 15 '13 at 10:38
how can I able to show that 251 satisfies the equation. –  poton Mar 15 '13 at 10:40
Simply write $503 \ |\ 3^{502}-1$ as 503 is prime –  Jean-Claude Arbaut Mar 15 '13 at 10:43

$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$.

-
@Inceptio. I had this answer in mind. But how do you decide that 503 divides the first factor, not the second ? Actually the GCD is not even necessary since 503 is prime. –  Jean-Claude Arbaut Mar 15 '13 at 10:54
Thats just because $3^{502}\equiv1\pmod {503}$. From the the same fermat's theorem. –  Inceptio Mar 15 '13 at 10:55
Ok, but your answer has nothing to do with this last argument ;-) –  Jean-Claude Arbaut Mar 15 '13 at 10:57
Yeah! . I assumed people know the theorem. :P –  Inceptio Mar 15 '13 at 10:58
$3^{502}\equiv1\pmod {503}$ right? Which means the other factor doesn't divide $503$, as the G.C.D is $2$ and $503$ is prime.! –  Inceptio Mar 15 '13 at 11:01

$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.

-
Awesome. Use of Sophie Germain prime fascinates me. –  Inceptio Mar 18 '13 at 4:14

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$

-