Compute 3^1000 (mod13)

Question

I'm unsure how to compute the following : 3^1000 (mod13)

I tried working through an example below,

ie) Compute $3^{100,000} \bmod 7$ $$ 3^{100,000}=3^{(16,666⋅6+4)}=(3^6)^{16,666}*3^4=1^{16,666}*9^2=2^2=4 \pmod 7\\ $$

but I don't understand why they divide 100,000 by 6 to get 16,666. Where did 6 come from?

Answer 1

Fermat's Little Theorem says that: $$a^p \equiv a\pmod{p}$$ Or, that: $$a^{p-1}\equiv 1\pmod{p}$$ You're looking at this mod $7$, so $3^{7-1} = 3^6\equiv 1\pmod{p}$. So, we're trying to split $100,000$ into $6k+r$ where $0\leq r < 5$, which is what writing $100,000 = 16,666\times 6+4$.

Answer 2

Just use Fermat's Little Theorem

$a^{p}\equiv a\mod p$

with $p=7$ in your example and $p=13$ in your former question.

Answer 3

There is a fast&brutal solution that requires very little knowledge: $$ 3^{1000} \equiv 3\cdot(3^3)^{333} \equiv 3\cdot 1^{333} \equiv \color{red}{3}\pmod{13}.$$ A similar approach works in the other case, too: $$ 3^{10000}\equiv 3\cdot(3^3)^{3333} \equiv 3\cdot(-1)^{3333} \equiv -3\equiv \color{red}{4}\pmod{7}.$$