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

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.