Question

Как найти остаток при делении 3^22 на 7 ?

Answer 1

$3^{22}=9^{11}=(7+2)^{11}=7^{11}+C_{11}^1*7^{10}*2+...+C_{11}^k7^{11-k}2^k+...$
$+C_{11}^{10}*7*2^{10}+2^{11}=7*A+2^{11}=7A+2^3*2^8=$
$=7A+(7+1)*2^8=7A+7*2^8+2^8=7A+7*2^8+7*2^5+7*2^2+$
$+2^2=7*B+4$
Значит, остаток от деления 3^22 на 7 равен 4