Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section17.2The Division Algorithm

Recall that the division algorithm for integers (Theorem 2.9) says that if \(a\) and \(b\) are integers with \(b \gt 0\), then there exist unique integers \(q\) and \(r\) such that \(a = bq+r\), where \(0 \leq r \lt b\). The algorithm by which \(q\) and \(r\) are found is just long division. A similar theorem exists for polynomials. The division algorithm for polynomials has several important consequences. Since its proof is very similar to the corresponding proof for integers, it is worthwhile to review Theorem 2.9 at this point.


The division algorithm merely formalizes long division of polynomials, a task we have been familiar with since high school. For example, suppose that we divide \(x^3 - x^2 + 2 x - 3\) by \(x - 2\).

\(x^2\) \(+\) \(x\) \(+\) \(4\)
\(x\) \(-\) \(2\) \(x^3\) \(-\) \(x^2\) \(+\) \(2x\) \(-\) \(3\)
\(x^3\) \(-\) \(2x^2\)
\(x^2\) \(+\) \(2x\) \(-\) \(3\)
\(x^2\) \(-\) \(2x\)
\(4x\) \(-\) \(3\)
\(4x\) \(-\) \(8\)

Hence, \(x^3 - x^2 + 2 x - 3 = (x - 2) (x^2 + x + 4 ) + 5\).

Let \(p(x)\) be a polynomial in \(F[x]\) and \(\alpha \in F\). We say that \(\alpha\) is a zero or root of \(p(x)\) if \(p(x)\) is in the kernel of the evaluation homomorphism \(\phi_{\alpha}\). All we are really saying here is that \(\alpha\) is a zero of \(p(x)\) if \(p(\alpha) = 0\).

Let \(F\) be a field. A monic polynomial \(d(x)\) is a greatest common divisor of polynomials \(p(x), q(x) \in F[x]\) if \(d(x)\) evenly divides both \(p(x)\) and \(q(x)\); and, if for any other polynomial \(d'(x)\) dividing both \(p(x)\) and \(q(x)\), \(d'(x) \mid d(x)\). We write \(d(x) = \gcd( p(x), q( x))\). Two polynomials \(p(x)\) and \(q(x)\) are relatively prime if \(\gcd(p(x), q(x) ) = 1\).

Notice the similarity between the proof of Proposition 17.10 and the proof of Theorem 2.10.