Делимость на 16

[Lazy]

Мне сильно стыдно, но не могу решить следующую простую задачу: показать, что выражение $3^{2n+2}+8n-9$ делится на 16 при любом натуральном $n$.

Подозреваю, что это доказывается по индукции. А именно, проверяем для $n = 1$ (верно), полагаем что верно и для $n$. Проверим для $n+1$ - получим выражение: $3^{2(n+1)+2}+8(n+1)-9 = 3^{2n+4}+8n-1$. Как показать делимость - ума не приложу

Я пытался использовать что $16 = 2^4$, что 3 в нечетной степени - 1 есть всегда четное число и детально проверил делимость при $n$ от 1 до 10, в надежде усмотреть закономерность... Тщетно. Очевидно, нужно как-то вынести множитель $2^4$, что докажет и делимость, но как?

[Andrei666]

да тут можно так, рассмотри разность двух выражений, которые идут друг за другом(эн отлична на единику)- там выносится восьмерка, и теперь докажи делимость на два второй части

[Lazy]

То есть, разность выражений будет $3^{2n+2}(3^2-1)-8 = 8(3^{2n+2}-1)$. Число в скобках всегда четное, значит делится на 2, а значит можно вынести еще двойку и получим делимость на 16?

Мде... Простоватый я парень, оказывается. Спасибо!

[Andrei666]

Да!

[Null]

$3^{2n+2}(3^2-1)+8 = 8(3^{2n+2}+1)$

а я сижу голову ломаю почему не сходиться.

[ewert]

А вот по рабоче-крестьянски. Давайте-ка прикинем остатки от деления этого выражения на $16$. Со слагаемым $8n$ всё ясно,с девяткой -- тем более, так что сосредоточимся на $3^{2n+2}$.

При $n=-1$ получаем $r_{-1}=3^0\mod16=1$.
При $n=0$ имеем $r_{0}=r_{-1}\cdot9\mod16=9\mod16=9$.
При $n=1$ получается $r_{1}=r_{0}\cdot9\mod16=81\mod16=1$.
Соответственно, при $n=2$ выйдет $r_{2}=r_{1}\cdot9\mod16=9\mod16=9$.

Дальше остатки, естественно, периодически повторяются. Т.е.: остаток от деления $3^{2n+2}$ на $16$ равен $1$ для нечётного $n$ и $9$ для чётного.

Т.е. остаток от деления $(3^{2n+2}-9)$ на $16$ равен $8$ для нечётного $n$ и $0$ для чётного. Но ведь и для слагаемого $8n$ будет ровно так же. Следовательно -- для всей суммы остаток всегда нулевой, ч.т.д.

[Утундрий]

Еще более по рабоче-крестьянски: четыре раза применить признак делимости на два...

[Lazy]

Утундрий
Хорошо, это интересно. Вы не могли бы привести свое решение?

[Утундрий]

Lazy в сообщении #404081 писал(а):

Вы не могли бы привести свое решение?

У меня, видите ли, нет своего решения. И, смею заверить, не будет. Я, некоторым образом, таких задач не решаю. Принципиально.