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$?
-
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.
-
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.
-
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?
-
0@mohabitar: try $3^k\mod 7$ for $k=1,2,3,...$ and see what happens. – 2011-01-23