1/4 финала. Вариант 2 (8)

Докажем более сильное утверждение: 3ⁿ + 1 при четном n делится на 2, при нечетном n делится на 2², но в обоих случаях не делится ни на какую более высокую степень двойки.

Квадрат нечетного числа при делении на 8 дает остаток 1. Тогда:

а) если n = 2m, то 3ⁿ + 1 = (3^m)² + 1 = (8a + 1) + 1 = 2(4a + 1) — делится на 2, но не делится на 4;
б) если n = 2m + 1, то 3ⁿ + 1 = 3 × (3^m)² + 1 = 3 × (8a + 1) + 1 = 4 × (6a + 1) — делится на 4, но не делится на 8.

Требуемое утверждение — частный случай доказанного.