Найти остаток от деления числа a=3×2^73+9×16^29 на 17

Предыдущий
вопрос Следующий
вопрос

Для того чтобы найти остаток от деления данного числа на 17, нужно преобразовать выражение a=3×2^73+9×16^29:

a = 32^73 + 916^29 = 32^73 + 9(2^4)^29 = 3(2^72)2 + 9*(2^116)

Теперь заметим, что 2^4 = 16 = -1 (mod 17), так как 16 = 1 (mod 17), и 2^72 = (2^4)^18 = 1^18 = 1 (mod 17), а также 2^116 = 2^4*29 = (-1)^29 = -1 (mod 17).

Теперь подставим это в выражение a:

a = 312 + 9*(-1) = 6 - 9 = -3

Так как остаток должен быть положительным числом, то можно добавить к -3 нужное количество 17, чтобы получить положительный остаток:

-3 + 17 = 14

Итак, остаток от деления числа a на 17 равен 14.