Рассмотри 4^n = (1+3)^n = 1^n + n*3 + ...
Остальные члены биноминального разложения всегда делятся на 9, в отличие от первых двух. Т.к. там будет 3 в степени 2 и выше.
Остаётся выражение (1 + n*3), которое само по себе не всегда делится на 9.
1 + 3n + 6n - 1= 9n
9n всегда делится на 9 при любых n.