Zgodnie z treścią zadania, reszta z dzielenia liczby $n$ przez 3 jest równa 1. Oznacza to, że $n$ można zapisać w postaci:\[n = 3k + 1\]gdzie $k$ jest liczbą całkowitą nieujemną ($k \ge 0$).Chcemy wykazać, że reszta z dzielenia liczby $4^n$ przez 9 jest równa 4. To jest równoważne wykazaniu, że $4^n - 4$ jest podzielne przez 9. Podstawiamy wzór na $n$:\[4^n - 4 = 4^{3k+1} - 4\]Wyciągamy 4 przed nawias:\[4^{3k+1} - 4 = 4 \cdot 4^{3k} - 4 = 4 \cdot (4^{3k} - 1)\]Zauważmy, że $4^{3k} = (4^3)^k = 64^k$. Zatem wyrażenie przyjmuje postać:\[4 \cdot (64^k - 1)\]Aby $4 \cdot (64^k - 1)$ było podzielne przez 9, a ponieważ 4 i 9 są względnie pierwsze, wyrażenie $(64^k - 1)$ musi być podzielne przez 9. Korzystamy ze wzoru skróconego mnożenia na różnicę $k$-tych potęg: $a^k - b^k = (a-b)(a^{k-1} + a^{k-2}b + \dots + b^{k-1})$. Dla $a=64$ i $b=1$:\[64^k - 1 = (64-1)(64^{k-1} + 64^{k-2} \cdot 1 + \dots + 1^{k-1})\]\[64^k - 1 = 63 \cdot (64^{k-1} + 64^{k-2} + \dots + 1)\]Niech $M = (64^{k-1} + 64^{k-2} + \dots + 1)$. $M$ jest liczbą całkowitą dla $k \ge 1$. Zatem $64^k - 1 = 63M$. Ponieważ $63$ jest podzielne przez 9 ($63 = 9 \cdot 7$), to $63M$ jest podzielne przez 9. A więc, $(64^k - 1)$ jest podzielne przez 9 dla $k \ge 1$.Teraz wracamy do $4 \cdot (64^k - 1)$:\[4 \cdot (64^k - 1) = 4 \cdot (9 \cdot 7 \cdot M) = 9 \cdot (28M)\]Wyrażenie $9 \cdot (28M)$ jest podzielne przez 9.To dowodzi, że $4^n - 4$ jest podzielne przez 9 dla $k \ge 1$. Rozważmy przypadek $k=0$. Wtedy $n = 3 \cdot 0 + 1 = 1$. Wówczas $4^n - 4 = 4^1 - 4 = 4 - 4 = 0$. Liczba 0 jest podzielna przez 9.Zatem dowód jest prawdziwy dla wszystkich liczb całkowitych nieujemnych $k$.