Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
$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
1  
Simply write $503 \ |\ 3^{502}-1$ as 503 is prime –  Jean-Claude Arbaut Mar 15 '13 at 10:43

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
@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
1  
$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.

share|improve this answer
    
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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.