# How to find $3^{1000}\bmod 7$?

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.

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

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.

-
Once again, I'll ask for future reference: Is there a particular reason for the downvote? –  Arturo Magidin Jan 23 '11 at 2:06
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.

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

-

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

-
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