I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two:
- $13^{100} \bmod 7$
- $7^{100} \bmod 13$
I've also heard of this formula:
$$a \equiv b\pmod n \Rightarrow a^k \equiv b^k \pmod n $$
But I don't see how exactly to use that here, because from $13^1 \bmod 7$ I get 6, and $13^2 \bmod 7$ is 1. I'm unclear as to which one to raise to the kth power here (I'm assuming k = 100?)
Any hints or pointers in the right direction would be great.
Best Answer
The formula you've heard of results from the fact that congruences are compatible with addition and multiplication.
The first power $13^{100}$ is easy: $13\equiv -1\mod 7$, so $$13^{100}\equiv (-1)^{100}=1\pmod 7.$$
The second power uses Lil' Fermat: for any number $a\not\equiv 0\mod 13$, we have $a^{12}\equiv 1\pmod{13}$, hence $$7^{100}\equiv 7^{100\bmod12}\equiv 7^4\equiv 10^2\equiv 9\pmod{13}$$