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$. –  user63477 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. –  user63477 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
add comment

3 Answers

up vote 5 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. –  user63477 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 –  user63477 Mar 15 '13 at 10:58
    
@inceptio, how do you establish that prime $503\not\mid (9^{251}+1)?$ –  lab bhattacharjee Mar 15 '13 at 10:59
show 8 more comments

$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. –  user63477 Mar 18 '13 at 4:14
add comment

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
add comment

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.