Question

                          Найдите наибольший остаток числа 3^(2n+2)+8n−6 при делении на 16, где n — любое натуральное число.

Answer 1

3.

В действительности при любом натуральном n остаток равен 3. Докажем это по индукции:
База. n = 1: 3^4 + 8 - 6 = 83 даёт остаток 3 при делении на 16.
Переход. Пусть при n = k выражение даёт остаток 3. Найдём остаток при n = k + 1.
3^(2(k + 1) + 2) + 8(k + 1) - 6 = 9 * (3^(2k + 2) + 8k - 6) - 72k + 54 + 8k + 8 - 6 = 9 * (3^(2k + 2) + 8k - 6) - 64k + 56 = ...
По предположению индукции выражение в скобках равно 16m + 3 для какого-то целого m. 
... = 9 * (16m + 3) - 64k + 60 = 144m + 27 - 64k + 56 = 16(9m - 4k + 5) + 3
Очевидно, это выражение даёт остаток 3 при делении на 16, индукционный переход доказан.
Тогда по принципу математической индукции выражение дает остаток 3 при любом натуральном n.