Prove that $ 16^{20}+29^{21}+42^{22}$ is divisible by $13$.

Question

Prove that $ 16^{20}+29^{21}+42^{22}$ is divisible by $13$.

This is not a homework question. I would like to know how to solve this type of problems, I solved similar problem with n in exponent, but that could be proved by induction. Here I guess, Euler's theorem could be useful, but I can't work it out. Could anybody give me a hint of how to solve it?

Answer 1

$16 \equiv 29 \equiv 42 \equiv 3 \text{ mod } 13$. Thus, the claim follows from $3^{20}+3^{21}+3^{22}=3^{20}(1+3+9)=3^{20}13$.

Answer 2

HINT Notice the difference its $13$ so now perform modular division and your proof is done. As suggested by Plankton

Answer 3

$(16^{20}+29^{21}+42^{22})\text{ mod }13=(3^{20}+3^{21}+3^{22})\text{ mod }13$

$3^{20}(3^{0}+3^{1}+3^{2}) \text{ mod }13=3^{20}13\text{ mod }13$

$16^{20}+29^{21}+42^{22}=0\text{ mod }13$