多項式 A, B を除法の原理に基づき A = BQ + R としたときに、
(A, B) \simeq (B, R)
証明
(A, B) = G とおく。A = GA', \ B = GB' と表すことができ、整数の場合と同様にして (A', B') = 1 が分かる。したがって、
A = BQ + R \iff GA' = GB'Q + R \iff R = G(A' - B'Q) より、R は G を因数に持つ。よって G は B, R の公約多項式。
(B, R) = G' とおけば、初等整数論/多項式の定理 4 より G' = GEと表せる。 初等整数論/多項式の定理 ii から |G'| \geqq |G| \cdots (1).
一方、B = G'C, \ R = G'R' と表すことができ、A = BQ + R \iff A = G'(C + R') より、G' は A, B の公約多項式。定理 4 から G = G'E'と表せる。 定理 ii によって |G'| \leqq |G| \cdots (2).
(1), (2) によって G \simeq G' が導かれる。
定理 8 は飛ばす。
(A, B) = G としたとき、AX + BY = Cが解を持つこととG \, | \, Cは同値。
証明
AX + BY = C のとき A = GA', \ B = GB' とすれば AX + BY = C \iff G(A'X + B'Y) = C より、G \, | \, C.
逆に G \, | \, C のとき C = GC' とおく。AX + BY = G が解を持つならば、A(XC') + B(YC') = GC' = C となるので、AX + BY = G が解を持つことを示せれば良い。
議論は整数の場合とさほど変わらないので省略すると、ユークリッドの互除法を用いて得られた逐次商 Q_1, Q_2, \cdots , Q_k を用いて
x_1 = 1, \ \ y_1 = q_1, \ \  x_2 = -q_2, \ \  y_2 = 1 + q_1 q_2
x_k = x_{k-2} - x_{k-1}q_k, \ \ y_k = y_{k-2} - y_{k-1}q_k \ \ \ (k \geqq 3)
で求められる。
整数の場合と違うのは、ユークリッドの互除法が B の次数以下の手数で終わるということがはっきりする点である。
例
A = x^2 + 2, \ B = x^2 + x + 1 に対してユークリッドの互除法を行う。
\begin{align}
A & = B - (x-1) \\
B & = (x-1)(x+2) + 3
\end{align}
余りを主体にすると
\begin{align}
(x-1) & = B - A \\
3 & = -(x-1)(x+2) + B
\end{align}
一番目の式を二番目の式に代入して A(x + 2) + B(-x - 1) = 3 \iff A \left( \frac{1}{3}x + \frac{2}{3} \right) + B \left( -\frac{1}{3}x - \frac{1}{3} \right) = 1.
実際 (x^2 + 2)(x + 2) + (x^2 + x + 1)(-x - 1) = (x^3 + 2x^2 + 2x + 4) - (x^3 + 2x^2 + 2x + 1) = 3.
既約多項式とは、それ以上因数分解できない多項式のことをいう。
例
は有理数上既約多項式である。しかし x^3 + 2 は実数上既約ではない。 x + \sqrt[3]{2} を因数に持つからである。また最初のものを除いて、いずれの多項式も複素数上既約ではない。1次の因数に分解できるからである。また
という数の集まりを考えると、これも有理数、実数、複素数と同様に0以外の数で割り算ができる（すなわち代数体である）ので、ここでの議論が有理数、実数、複素数と同様に通用するが、上記の最後の例は
{2}x+2 \right)
と因数分解できるので、\mathbb Q (\sqrt{5}) 上既約ではない（しかし、右辺の2次の因数はいずれも \mathbb Q (\sqrt{5}) 上既約である）。
既約多項式に対して、因数分解できる多項式を可約多項式という。
既約多項式は重解を持たない。というのは P(x) が重解を持つなら \gcd(P, P')>1 となるが、|P'|=|P|-1 なので \gcd(P, P') は P(x) の自明でない因数となってしまうからである。
さて、既約多項式と因数分解について、次の事実は比較的容易に示される。
任意の可約多項式は既約多項式に因数分解される。
証明
任意の可約な二次多項式 A について、定理 ii より、A = BC のとき |A| = |B| + |C| だが、
|A| = 2 なので |B| = |C| = 1 、すなわち2つの一次式に因数分解される。任意の一次式は既約多項式なので、二次式の場合はこの定理の主張を満たす。
次に n 次未満の全ての多項式においてこの定理が成り立っていたとする。このとき、任意の n 次可約多項式を A とする。
仮定より A = BC となり、|B|, |C| \ \geqq 1 、定理 ii より |A| = |B| + |C| なので |B|, |C| \ < n.
この2つの多項式が既約か可約に関わらず、帰納法の仮定から結局 A は既約多項式に分解されることが証明される。
----
さて、一次式はみな既約多項式だが、高次多項式で既約多項式は無限に存在するのだろうかという疑問は自然に湧いてくる。その証明はひとまず後回しにするとして、因数分解の一意性の証明に迫る。
P を任意の既約多項式とする。
P \, | \, AB \Rightarrow P \, | \, A \vee P \, | \, B
証明
既約多項式の定義より (A, P) = 1または(A, P) = P である。
(A, P) = P の場合、定理の主張を満たす。
(A, P) = 1 の場合、定理 9 から AX + PY = 1 となる X, Y が存在する。したがって
ABX + BPY = B ここで仮定より PK = AB とおくと P(KX + BY) = B.
以上より定理は示された。
この定理を用いて、因数が ABC \cdots といくつになっても数学的帰納法より同様の定理が得られる。
全ての多項式は、定数項・順序を無視すればただ一通りに既約多項式に分解される。
証明
仮に、ある多項式 A(x) が既約多項式に二通りに分解されたとしよう。
A \simeq P_1P_2 \cdots P_n \simeq Q_1Q_2 \cdots Q_m
n \leqq m としても一般性を失わない。
P_1 \, | \, Q_1Q_2 \cdots Q_m
なので、定理 12 から
P_1 \, | \, Q_1 \vee P_1 \, | \, Q_2 \vee \cdots \vee P_1 \, | \, Q_m
P_1 \, | \, Q_1 として一般性を失わない。どちらも既約多項式なので P_1 \simeq Q_1.よって、
P_2P_3 \cdots P_n \simeq Q_2Q_3 \cdots Q_m
同様に、
P_2 \, | \, Q_2 \vee P_2 \, | \, Q_3 \vee \cdots \vee P_2 \, | \, Q_m.
であり、P_2 \, | \, Q_2として一般性を失わず、P_2 \simeq Q_2.である。以下同様にP_n \simeq Q_nまでが得られる。
ところで定理 ii より |P_1P_2 \cdots P_n| = |Q_1Q_2 \cdots Q_m| \iff |P_1| + \cdots |P_n| = |Q_1| + \cdots + |Q_m| となり、先ほどの議論から
|P_1| = |Q_1|, |P_2| = |Q_2|, \cdots |P_n| = |Q_n| なので
|Q_{n+1}| = \cdots = |Q_m| = 0.
すなわち n = m が得られ、また P_1 \simeq Q_1,P_2 \simeq Q_2,\cdots,P_n \simeq Q_n  より、因数分解の一意性が得られた。
除法の原理から、係数が有理数であれば、有理数上で既約な多項式の積に分解される。このことは有理数に限らず、実数や複素数、および任意の代数体上で成り立つ。特に複素数体上では、代数学の基本定理より、任意の多項式が定数と1次式の積に一意的に分解される。
さらに、整数係数の多項式は整数係数の、有理数上既約な多項式の積に分解されるが、これは後に合同多項式の理論を用いて示す。