How do you mod polynomials by another polynomial?

Question

I'm struggling to understand the concept behind questions of the form $f(x) = g(x) \bmod h(x)$. The example I have infront of me states

"... note that $x\cdot x = x+1$ since $x^2 \bmod (x^2+x+1) = x+1$"

It looks super simple but I think I'm missing just one small key bit of information yet I can't find it anywhere?

I forgot to include that they are in a field of characteristic 2

Any direction would be appreciated!

Answer 1

This is wrong, unless the coefficients are in a field of characteristic 2.

$$ x^2 + x + 1 \equiv 0 \pmod {x^2 + x + 1} $$ $$ x^2 \equiv -x-1 \pmod {x^2 + x + 1} $$

Answer 2

To understand modding by polynomials, first let's recall how modding by numbers works: We say $a \equiv b \mod n$ if $a-b$ is a multiple of $n$. For polynomials, it works exactly the same way:$$ f(x) \equiv g(x) \mod h(x) \Longleftrightarrow f(x)-g(x) \text{ is a multiple of }h(x) $$ There's a well-defined notion of "is a multiple of" for polynomials, just like there is for integers, and just like integers, the set of polynomials that are multiples of $h(x)$ is an ideal subring of the full polynomial ring, thus equivalence mod $h(x)$ respects addition and multiplication.

In this example, $$ x+1 \equiv x^2 \mod (x^2 + x+1) $$ is saying $x^2 - (x+1)$ is a multiple of $x^2+x+1$. Since you're in a field with characteristic 2, $1=-1$, so this is true (in fact, $x^2 - (x+1) = x^2 + x + 1$).

Answer 3

To answer the question in the title, to find $g(x) \bmod h(x)$, use polynomial division and write $g(x) = q(x)h(x)+r(x)$, with $r(x)=0$ or $\deg r(x) < \deg h(x)$. Then $r(x)$ is the reduction you seek: $r(x)= g(x) \bmod h(x)$.