# Easiest way to perform Euclid's division algorithm for polynomials

Let's say I have the two polynomials $f(x) = x^3 + x + 1$ and $g(x) = x^2 + x$ over $\operatorname{GF}(2)$ and want to perform a polynomial division in $\operatorname{GF}(2)$.

What's the easiest and most bullet proof way to find the quotient $q(x) = x + 1$ and the remainder $r(x)=1$ by hand?

The proposal by the german edition of Wikipedia is rather awkward.

-

$f$ corresponds to the binary number $1011$ and $g$ to $110$ if you identify $x$ with $2$. Appending a $0$ (rsp. multiplication by $2$) corresponds to multiplying with $x$ and $\oplus$ (exclusive or) is addition.

1011:110 = 11, i.e., the quotient is $x+1$
110
---
111
110
---
1, i.e., the remainder is 1
-

Polynomial long division is the way to go. Especially over a finite field where you don't have to worry about fractional coefficients (working over for instance the rational numbers these can get extremely unwieldy surprisingly soon). Over $\mathbb Z/2\mathbb Z$ you don't even have to worry about dividing coefficients at all, the only question to be answered is "to substract or not to subtract", where as a bonus subtraction is actually the same as addition.

Note that the wikipedia article you refer to does not assume such a simple context, and avoids division by coefficients by doing a pseudo-division instead (for which instead of explosion of fractions you can get enormous coefficients).

-