I needed to evaluate $3^{100} \pmod 7$ by hand.
So, I made a list of increasing powers of $3 \pmod 7$ like so:
- $3^1 \equiv 3 \pmod 7$
- $3^2 \equiv 2 \pmod 7$
- $3^3 \equiv 6 \pmod 7$ (1)
- ...
- $3^6 \equiv 1 \pmod 7$ (2)
As soon as I discovered (2), I knew I had enough information to take care of the original problem:
$$3^{100} \equiv (3^6)^{16}3^4 \equiv (1)^{16}3^4 \equiv 4 \pmod 7.$$
However, I noted while writing down (1): $3^3 \equiv 6 \equiv -1 \pmod 7$.
I thought this could also solve the original problem, but found it was inconsistent with my first answer:
$$3^{100} \equiv (3^3)^{33}3^1 \equiv (-1)^{33}3^1 \equiv 3 \pmod 7.$$
My gut tells me my arithmetic is wrong or I'm completely missing something.
Can anyone explain the inconsistency?
Note that $(-1)^{33} = - 1$, so $(-1)^{33}3^1 = -3$, not $3$ as you've written above. This is consistent as $-3 \equiv 4 \pmod 7$.