Для начала заметим, что при делении числа на 4 остаток может быть только 0, 1, 2 или 3.

При n = 1:
3^1 + 5^1 + 7^1 + 9^1 = 3 + 5 + 7 + 9 = 24, что делится на 4 без остатка.

Предположим, что для некоторого k это утверждение верно, то есть 3^k + 5^k + 7^k + 9^k кратно 4.

Докажем, что это верно и для k+1:
3^(k+1) + 5^(k+1) + 7^(k+1) + 9^(k+1) = 33^k + 55^k + 77^k + 99^k = 33^k + 55^k + 77^k + 99^k = 3(3^k + 5^k + 7^k + 9^k) + 2(3^k + 5^k + 7^k) = 2(3^k + 5^k + 7^k) (по предположению) = 24m = 8m, где m - целое число.

Таким образом, мы доказали, что число, заданное выражением 3^n + 5^n + 7^n + 9^n, кратно 4 при любом натуральном n.