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.
How to find $3^{1000}\bmod 7$?
-
0Here's a hint: find the number $k$ such that $3^k = 1$. – 2011-01-23
-
0@Eric wouldnt that just be 0? – 2011-01-23
-
2that's true, let me rephrase: find a positive number $k$ such that $3^k = 1$ (mod 7). – 2011-01-23
4 Answers
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.
-
0Once again, I'll ask for future reference: Is there a particular reason for the downvote? – 2011-01-23
-
1dunno about the down vote. But in the last tep, since $3^6 = 1$ wouldn't it be better to factor $1000 = 4 mod 6$? – 2011-01-23
-
0@Willie: Oops; quite right. That was silly of me. – 2011-01-23
-
0Just 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 – 2011-01-24
-
0@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)$. – 2011-01-24
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.
-
0How much more could I simplify $3^{10}$ though? – 2011-01-23
-
0$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. – 2011-01-23
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?
-
0Well 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. – 2011-01-23
-
0@mohabitar: try $3^k\mod 7$ for $k=1,2,3,...$ and see what happens. – 2011-01-23