"Smart" solution for $7^{100}+11^{100} \pmod{13}$?

Solution 1:

You can speed up the first step a lot by knowing Fermat's little theorem.

It states that if $p$ is a prime then for any $n$ we have:

$$a^{n-1}\equiv1\pmod{p}$$

In your problem $13$ is a prime so we can use it:

$7^{12}\equiv1\pmod{13}$ and $11^{12}\equiv\pmod{13}$

Then note that $100\equiv4\pmod{12}$ and you get to your solution.

You still need to work out $7^4\pmod{13}$ and $11^4\pmod{13}$.

Solution 2:

Thank to the guys at the comment section, the improved solution is the following: $$ 7^{100} + 11^{100}$$ $$= 7^{8 \cdot (13-1) + 4} + 11^{8 \cdot (13-1) + 4}$$ $$ \equiv 7^4 + 11^4$$ $$ \equiv (7^2)^2 + (-2)^4 $$ $$\equiv 10^2 + 16$$ $$\equiv 9 + 3 = 12 \pmod{13} $$