How to solve $x^r [ x^n + 1] = x^{r[n]}$

Question

I send this message to have a piece of advice to solve my problem. Here is the statement:

Assume $k$ belongs to $N$ and $GF(2^k)[x]$ is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove, that if $r$ belongs to $N$, $n$ belongs to $N$, $n \geq 2$ and $x^r$ is a polynomial from the ring of polynomials $GF(2^k )[x]$, then we have:

$$x^r \bmod(x^n + 1) = x^{r \bmod (n)}.$$

I wanted to prove this by a proposition. Showing that's true for $n = 2$ and then showing that it's true for all $n \geq 2.$

I succeeded to prove this in case $r < 2$ because $x^r \bmod(x^n+1) = x^r$ and $r[n] = r$. But then I encounter an issue for $n =2$ and for greater I don't know how to prove this.

for $r = 2$ we have $x^r [ x^n + 1] = -1$ and $x^0 = 1.$

Thank you in advance

Answer 1

Hints:

• Show that for all positive integers $q$ the polynomial $x^{qn}-1$ is divisible by the polynomial $x^n-1$. Observe that we are in characteristic two, so $x^n-1$ and $x^n+1$ mean the same thing.
• Show that $x^{qn}\equiv1\pmod{x^n+1}$ for all positive integers $q$.
• Show that $x^{qn+b}\equiv x^b\pmod{x^n+1}$ for all positive integers $q,b$.
• We can write any integer $r$ in the form $r=qn+b$ where $q$ is an integer, and $b$ is the remainder of $r$ when divided modulo $n$.