Question

Пж помогите

Попробуйте решить без больших вычислений
докажите что 47^31 + 27^62 кратно 97

Answer 1

$27^{62} = 729^{31}$

$47 \mod 97 = 47\\729 \mod 97 = 50$

$(47 + 729) \mod 97 = 0$

Заметим, что т.к. степень нечётна, можно разложить нашу сумму как

$47^{31} + 729^{31} = (47 + 729)(47^{30} - 47^{29}729 + 47^{28}729^2 - \ldots - 47\cdot729^{29} + 729^{30})$

И так как $(47+729)$ делится на 97, то и $(47^n + 729^n)$ делится на 97 при нечётном $n$, в нашем случае $n = 31$