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.
$\endgroup$ 34 Answers
$\begingroup$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.
$\endgroup$ 5 $\begingroup$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.
$\endgroup$ 2 $\begingroup$Since that 36mod7=1, then we have 31000=36*166+4=34=4 mod7.
$\endgroup$ $\begingroup$$3^{1000}$ is hard to compute by hand because of the $1000$. Can you learn anything from trying smaller exponents instead?
$\endgroup$ 2
