Prove that $x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$ Assume $GF(2^k)[x]$ (where $k$ is a fixed natural number) is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove that for every polynomial $x^n$ (where $n \in \mathbb{N}$) from $GF(2^k)[x]$ we have
$$x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$$
Any idea? 
Thanks for your help.
 A: That equality it's used in cryptography to speed up calculations in the ring $GF(2^k)[x]/(x^4+1)$.
$GF(2^8)$, $GF(2^8)[x]$ and $GF(2^8)[x]/(x^4+1)$ are essential algebraic structures used in Advanced Encryption Standard (AES). The elements of $GF(2^8)$ are represented in computers as 8-bit words, whereas the elements of $GF(2^8)[x]/(x^4+1)$ as 32-bit words.
Prove:


*

*In $Z_2=\{0,1\}$, addition operation (denoted with "$\oplus$") is simply a sum modulo 2. Subtraction operation (denoted with "$\ominus$") is equivalent to addition. Because $1 \oplus 1 = 0$ and $0 \oplus 0 = 0$, so $-a=a$, ($a \in Z_2$), then $a \ominus b = a \oplus b$, ($a,b \in Z_2$).

*In $GF(2^k)$, (whose elements are the words of binary length $k$), we define addition operation as the sum of polynomials. In our case, the sum of the coordinates modulo 2. If $a=(a_1, a_2, ..., a_k) \in GF(2^k)$, where $a_i \in \{0,1\}$ and $b=(b_1, b_2, ..., b_k) \in GF(2^k)$, where $b \in \{0,1\}$, then we have:
$$ a+b=(a_1 \oplus b_1, a_2 \oplus b_2, ..., a_k \oplus b_k)$$
$$ a-b=(a_1 \ominus b_1, a_2 \ominus b_2, ..., a_k \ominus b_k)=(a_1 \oplus b_1, a_2 \oplus b_2, ..., a_k \oplus b_k)$$


*Of course, for $n<4$, the formula is true. For $n \ge 4$, there is a $q \in N$, that $n=q·4+r$ for $0 \le r \lt 4$, so $r=n \pmod 4$. Taking into account the point 2, we have:



and so indeed:
$$x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$$
