<s>[INST] "Smart" solution for $7^{100}+11^{100} \pmod{13}$? I have the following exercise: "Find $7^{100}+11^{100} \pmod{13}$".
My long and boring solution is the following:


*

*I've found that $7^k \equiv 7^{k \pmod{12}} \pmod{13}$ by calculating $7^k \pmod{13} = 7 \cdot (7^{k-1} \pmod{13}) \pmod{13}$ from $k=1$ until the remainder starts to repeat itself.

*The same for $11^k \equiv 11^{k \pmod{12}} \pmod{13}$

*Using the result from steps 1 and 2, $7^{100}+11^{100} \equiv 7^4+11^4 \equiv 9 + 3 \equiv 12 \pmod{13}$
Both steps 1 and 2 require a lot of calculations and I suspect that I've missed some clever trick to avoid them and to solve the exercise in a "smart" way.
Is there a way to improve my solution?
 [/INST] 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} $$
</s>