2
$\begingroup$

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?

$\endgroup$

3 Answers 3

7
$\begingroup$

$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$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$(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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .