Why do polynomials and integers both have a long division algorithm?

Question

The grade-school long division algorithm and the polynomial long division algorithm are identical, if I'm not mistaken. Why is this the case? Are the two algebraic structures identical in some sense? What other fields share this same division algorithm?

Answer 1

I think the algebraic structures you are looking for are called Euclidean domains.

An Euclidean domain $R$ doesn't need to be a field, but only a ring with a "euclidean function" $v : R \setminus \{0\} \longrightarrow \Bbb N$. In the case of $\Bbb Z$, $v$ is the absolute value. In the case of $\Bbb R[X]$, $v(\cdot)$ is the degree (of polynomials). As you can see, $\Bbb R[X]$ is not a field, but it is an Euclidean domain, meaning that the function $v$ satisfies :

$$\forall a,b \in \Bbb R[X] \quad \exists q,r \in \Bbb R[X] \quad a=qb+r \;\text{ such that } \; v(r) = 0 \text{ or } v(r)<v(q)$$ In the formula above, you can replace $\Bbb R[X]$ by any Euclidean domain $R$, because this is basically the definition. You can think of $r$ as the remainder and $q$ as the quotient.

Any field is a Euclidean domain, by defining $v(r) = 1$ for all $r≠0$.