Question

Докажите, что если целые числа a и b пи делении на натурально число  n дают равные остатки, то числа a^m и b^m, где m принадлежит N, при делении на n также дают равные остатки. Используя этот вывод, найдите остаток деления: а)  5^114 на 6  б)3^129 на 8

№346

Answer 1

То, что числа a и b дают одинаковые остатки при делении на n можно перефразировать так: a - b делится на n.
Тогда доказать нужно следующее: пусть a - b делится на n. Тогда и $a^m - b^m$ делится на n.
Для доказательства достаточно заметить, что $a^m - b^m$ при всех натуральных m делится на a - b: 
$a^m - b^m=(a -b)(a^{m-1}+a^{m-2}b+a^{m-3}b^2+cdots+ab^{m-2}+b^{m-1})$

а) 5 = -1 (mod 6)
Остаток такой же, что и у (-1)^114, т.е. 1
б) 3^129 = 3 * 9^64
9 = 1 (mod 8)
Остаток такой же, что и у 3 * 1^64, т.е. 3