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