Question

Докажите, что 9^30+6^19 делится на 7.

Answer 1

$9^{30}+6^{19} \equiv 2^{30}-1\mod 7$, а поскольку $2^{6} = 2^{\varphi(7)}\equiv 1 \mod 7$ по теореме Эйлера, то $2^{30}\equiv (2^{6})^{5} \equiv 1 \mod 7 \Leftrightarrow 2^{30}-1\equiv 0\mod 7$.