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.

Sorry this is a really simple problem but I couldnt figure it out. I'm trying to find the value of $3^{1000}\bmod 7$. I know the actual value is 4, but I used a calculator. How would I simplify this problem to get the correct answer without a calculator? I dont want a direct answer, but maybe a nudge in the right direction, such as tricks I could use or maybe an alternate way of writing it.

share|improve this question
    
Here's a hint: find the number $k$ such that $3^k = 1$. –  Eric O. Korman Jan 23 '11 at 0:58
    
@Eric wouldnt that just be 0? –  maq Jan 23 '11 at 1:09
1  
that's true, let me rephrase: find a positive number $k$ such that $3^k = 1$ (mod 7). –  Eric O. Korman Jan 23 '11 at 1:34

4 Answers 4

up vote 8 down vote accepted

If you know Fermat's Little Theorem, then you know you can reduce the exponent. If you don't, you can simply do a bit of testing: \begin{align*} 3 &\equiv 3 &\pmod{7}\\ 3^2 &\equiv 2&\pmod{7}\\ 3^3 &\equiv 2\times 3&\pmod{7}\\ &\equiv -1 &\pmod{7}. \end{align*} At this point, you will also know that $3^6 = (3^3)(3^3)\equiv (-1)^2 \equiv 1 \pmod{7}$.

That means that the remainders will "cycle" every seven steps, since $3^7 = 3(3^6) \equiv 3(1) = 3 \pmod{7}$.

So now, notice that since $1000 = 6(166) + 4$, then $$3^{1000} = 3^{6(166)+4} = (3^6)^{166}3^4 = (3^6)^{166}3^33^1.$$ You know what each of the factors is modulo $7$, so you're done.

share|improve this answer
    
Once again, I'll ask for future reference: Is there a particular reason for the downvote? –  Arturo Magidin Jan 23 '11 at 2:06
1  
dunno about the down vote. But in the last tep, since $3^6 = 1$ wouldn't it be better to factor $1000 = 4 mod 6$? –  Willie Wong Jan 23 '11 at 3:00
    
@Willie: Oops; quite right. That was silly of me. –  Arturo Magidin Jan 23 '11 at 4:58
    
Just got around to actually read this answer in detail, and I found myself very confused :( I thin you used a lot of tricks that I have no idea how you used them, like $(3^3)(3^3)$ is congruent to $(-1)^2$..but I guess this is a complicated problem anyway –  maq Jan 24 '11 at 6:15
    
@mohabitar: It's not really complicated. The "trick", as you call it, is just that you can add and multiply congruences: if $a\equiv b$ and $c\equiv d$, then $a+c\equiv b+d$ and $ac\equiv bd$ (if they are modulo the same thing). Since $3^3\equiv -1$, which we figure out just be computing, then $(3^3)(3^3)\equiv (-1)(-1)$. –  Arturo Magidin Jan 24 '11 at 14:04

Try to split the huge number in smaller numbers you know the value of. For example

$3^{1000} \text{mod} 7= (3^{10})^{100} \text{mod} 7= (59049)^{100} \text{mod} 7= 4^{100} \text{mod} 7 = \ldots$

If $3^{10}=59049$ was still too big you could try to rewrite it again etc.

share|improve this answer
    
How much more could I simplify $3^{10}$ though? –  maq Jan 23 '11 at 1:08
    
$3^{10}\equiv 3^3\cdot 3^3\cdot 3^3 \cdot 3\equiv 6\cdot 6 \cdot 6 \cdot 3 \equiv 36 \cdot 18 \equiv 1 \cdot 4 \equiv 4 (\text{mod} 7)$ for example. –  Listing Jan 23 '11 at 1:13

Since that 36mod7=1, then we have 31000=36*166+4=34=4 mod7.

share|improve this answer

$3^{1000}$ is hard to compute by hand because of the $1000$. Can you learn anything from trying smaller exponents instead?

share|improve this answer
    
Well even I know that $3^{10}mod7$ is also 4, but I used a calculator for that too since $3^{10}$ is still a large number that I couldnt compute myself. –  maq Jan 23 '11 at 1:07
    
@mohabitar: try $3^k\mod 7$ for $k=1,2,3,...$ and see what happens. –  Isaac Jan 23 '11 at 1:29

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.