初等整数論/因数分解の一意性
ユークリッドの互除法

多項式 A , B {\displaystyle A,B} を除法の原理に基づき A = B Q + R {\displaystyle A=BQ+R} としたときに、
ユークリッドの互除法

( A , B ) ≃ ( B , R ) {\displaystyle (A,B)\simeq (B,R)}
ユークリッドの互除法

証明 ( A , B ) = G {\displaystyle (A,B)=G} とおく。 A = G A ′ , B = G B ′ {\displaystyle A=GA',\ B=GB'} と表すことができ、整数の場合と同様にして ( A ′ , B ′ ) = 1 {\displaystyle (A',B')=1} が分かる。したがって、
ユークリッドの互除法

A = B Q + R ⟺ G A ′ = G B ′ Q + R ⟺ R = G ( A ′ − B ′ Q ) {\displaystyle A=BQ+R\iff GA'=GB'Q+R\iff R=G(A'-B'Q)} より、 R {\displaystyle R} は G {\displaystyle G} を因数に持つ。よって G {\displaystyle G} は B , R {\displaystyle B,R} の公約多項式。
ユークリッドの互除法

( B , R ) = G ′ {\displaystyle (B,R)=G'} とおけば、初等整数論/多項式の定理 4 より G ′ = G E {\displaystyle G'=GE} と表せる。 初等整数論/多項式の定理 ii から | G ′ | ≧ | G | ⋯ ( 1 ) . {\displaystyle |G'|\geqq |G|\cdots (1).}
ユークリッドの互除法

一方、 B = G ′ C , R = G ′ R ′ {\displaystyle B=G'C,\ R=G'R'} と表すことができ、 A = B Q + R ⟺ A = G ′ ( C + R ′ ) {\displaystyle A=BQ+R\iff A=G'(C+R')} より、 G ′ {\displaystyle G'} は A , B {\displaystyle A,B} の公約多項式。定理 4 から G = G ′ E ′ {\displaystyle G=G'E'} と表せる。 定理 ii によって | G ′ | ≦ | G | ⋯ ( 2 ) . {\displaystyle |G'|\leqq |G|\cdots (2).}
ユークリッドの互除法

(1), (2) によって G ≃ G ′ {\displaystyle G\simeq G'} が導かれる。
最大公約多項式の表示式

定理 8 は飛ばす。
最大公約多項式の表示式

( A , B ) = G {\displaystyle (A,B)=G} としたとき、 A X + B Y = C {\displaystyle AX+BY=C} が解を持つことと G | C {\displaystyle G\,|\,C} は同値。
最大公約多項式の表示式

証明 A X + B Y = C {\displaystyle AX+BY=C} のとき A = G A ′ , B = G B ′ {\displaystyle A=GA',\ B=GB'} とすれば A X + B Y = C ⟺ G ( A ′ X + B ′ Y ) = C {\displaystyle AX+BY=C\iff G(A'X+B'Y)=C} より、 G | C . {\displaystyle G\,|\,C.}
最大公約多項式の表示式

逆に G | C {\displaystyle G\,|\,C} のとき C = G C ′ {\displaystyle C=GC'} とおく。 A X + B Y = G {\displaystyle AX+BY=G} が解を持つならば、 A ( X C ′ ) + B ( Y C ′ ) = G C ′ = C {\displaystyle A(XC')+B(YC')=GC'=C} となるので、 A X + B Y = G {\displaystyle AX+BY=G} が解を持つことを示せれば良い。
最大公約多項式の表示式

議論は整数の場合とさほど変わらないので省略すると、ユークリッドの互除法を用いて得られた逐次商 Q 1 , Q 2 , ⋯ , Q k {\displaystyle 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 {\displaystyle 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 ≧ 3 ) {\displaystyle x_{k}=x_{k-2}-x_{k-1}q_{k},\ \ y_{k}=y_{k-2}-y_{k-1}q_{k}\ \ \ (k\geqq 3)}
最大公約多項式の表示式

で求められる。
最大公約多項式の表示式

整数の場合と違うのは、ユークリッドの互除法が B {\displaystyle B} の次数以下の手数で終わるということがはっきりする点である。
最大公約多項式の表示式

例
最大公約多項式の表示式

A = x 2 + 2 , B = x 2 + x + 1 {\displaystyle A=x^{2}+2,\ B=x^{2}+x+1} に対してユークリッドの互除法を行う。
最大公約多項式の表示式

A = B − ( x − 1 ) B = ( x − 1 ) ( x + 2 ) + 3 {\displaystyle {\begin{aligned}A&=B-(x-1)\\B&=(x-1)(x+2)+3\end{aligned}}}
最大公約多項式の表示式

余りを主体にすると
最大公約多項式の表示式

( x − 1 ) = B − A 3 = − ( x − 1 ) ( x + 2 ) + B {\displaystyle {\begin{aligned}(x-1)&=B-A\\3&=-(x-1)(x+2)+B\end{aligned}}}
最大公約多項式の表示式

一番目の式を二番目の式に代入して A ( x + 2 ) + B ( − x − 1 ) = 3 ⟺ A ( 1 3 x + 2 3 ) + B ( − 1 3 x − 1 3 ) = 1. {\displaystyle 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 + 2 x 2 + 2 x + 4 ) − ( x 3 + 2 x 2 + 2 x + 1 ) = 3. {\displaystyle (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 {\displaystyle x^{3}+2} は実数上既約ではない。 x + 2 3 {\displaystyle x+{\sqrt[{3}]{2}}} を因数に持つからである。また最初のものを除いて、いずれの多項式も複素数上既約ではない。1次の因数に分解できるからである。また
既約多項式

という数の集まりを考えると、これも有理数、実数、複素数と同様に0以外の数で割り算ができる(すなわち代数体である)ので、ここでの議論が有理数、実数、複素数と同様に通用するが、上記の最後の例は
既約多項式

と因数分解できるので、 Q ( 5 ) {\displaystyle \mathbb {Q} ({\sqrt {5}})} 上既約ではない(しかし、右辺の2次の因数はいずれも Q ( 5 ) {\displaystyle \mathbb {Q} ({\sqrt {5}})} 上既約である)。
既約多項式

既約多項式に対して、因数分解できる多項式を可約多項式という。
既約多項式

既約多項式は重解を持たない。というのは P ( x ) {\displaystyle P(x)} が重解を持つなら gcd ( P , P ′ ) > 1 {\displaystyle \gcd(P,P')>1} となるが、 | P ′ | = | P | − 1 {\displaystyle |P'|=|P|-1} なので gcd ( P , P ′ ) {\displaystyle \gcd(P,P')} は P ( x ) {\displaystyle P(x)} の自明でない因数となってしまうからである。
既約多項式

さて、既約多項式と因数分解について、次の事実は比較的容易に示される。
既約多項式

任意の可約多項式は既約多項式に因数分解される。
既約多項式

証明 任意の可約な二次多項式 A {\displaystyle A} について、定理 ii より、 A = B C {\displaystyle A=BC} のとき | A | = | B | + | C | {\displaystyle |A|=|B|+|C|} だが、
既約多項式

| A | = 2 {\displaystyle |A|=2} なので | B | = | C | = 1 {\displaystyle |B|=|C|=1} 、すなわち2つの一次式に因数分解される。任意の一次式は既約多項式なので、二次式の場合はこの定理の主張を満たす。
既約多項式

次に n {\displaystyle n} 次未満の全ての多項式においてこの定理が成り立っていたとする。このとき、任意の n {\displaystyle n} 次可約多項式を A {\displaystyle A} とする。
既約多項式

仮定より A = B C {\displaystyle A=BC} となり、 | B | , | C | ≧ 1 {\displaystyle |B|,|C|\ \geqq 1} 、定理 ii より | A | = | B | + | C | {\displaystyle |A|=|B|+|C|} なので | B | , | C | < n . {\displaystyle |B|,|C|\ <n.}
既約多項式

この2つの多項式が既約か可約に関わらず、帰納法の仮定から結局 A {\displaystyle A} は既約多項式に分解されることが証明される。
既約多項式

さて、一次式はみな既約多項式だが、高次多項式で既約多項式は無限に存在するのだろうかという疑問は自然に湧いてくる。その証明はひとまず後回しにするとして、因数分解の一意性の証明に迫る。
既約多項式

P {\displaystyle P} を任意の既約多項式とする。
既約多項式

P | A B ⇒ P | A ∨ P | B {\displaystyle P\,|\,AB\Rightarrow P\,|\,A\vee P\,|\,B}
既約多項式

証明 既約多項式の定義より ( A , P ) = 1 {\displaystyle (A,P)=1} または ( A , P ) = P {\displaystyle (A,P)=P} である。
既約多項式

( A , P ) = P {\displaystyle (A,P)=P} の場合、定理の主張を満たす。
既約多項式

( A , P ) = 1 {\displaystyle (A,P)=1} の場合、定理 9 から A X + P Y = 1 {\displaystyle AX+PY=1} となる X , Y {\displaystyle X,Y} が存在する。したがって
既約多項式

A B X + B P Y = B {\displaystyle ABX+BPY=B} ここで仮定より P K = A B {\displaystyle PK=AB} とおくと P ( K X + B Y ) = B . {\displaystyle P(KX+BY)=B.}
既約多項式

以上より定理は示された。
既約多項式

この定理を用いて、因数が A B C ⋯ {\displaystyle ABC\cdots } といくつになっても数学的帰納法より同様の定理が得られる。
既約多項式

全ての多項式は、定数項・順序を無視すればただ一通りに既約多項式に分解される。
既約多項式

証明 仮に、ある多項式 A ( x ) {\displaystyle A(x)} が既約多項式に二通りに分解されたとしよう。
既約多項式

A ≃ P 1 P 2 ⋯ P n ≃ Q 1 Q 2 ⋯ Q m {\displaystyle A\simeq P_{1}P_{2}\cdots P_{n}\simeq Q_{1}Q_{2}\cdots Q_{m}}
既約多項式

n ≦ m {\displaystyle n\leqq m} としても一般性を失わない。
既約多項式

P 1 | Q 1 Q 2 ⋯ Q m {\displaystyle P_{1}\,|\,Q_{1}Q_{2}\cdots Q_{m}}
既約多項式

なので、定理 12 から
既約多項式

P 1 | Q 1 ∨ P 1 | Q 2 ∨ ⋯ ∨ P 1 | Q m {\displaystyle P_{1}\,|\,Q_{1}\vee P_{1}\,|\,Q_{2}\vee \cdots \vee P_{1}\,|\,Q_{m}}
既約多項式

P 1 | Q 1 {\displaystyle P_{1}\,|\,Q_{1}} として一般性を失わない。どちらも既約多項式なので P 1 ≃ Q 1 . {\displaystyle P_{1}\simeq Q_{1}.} よって、
既約多項式

P 2 P 3 ⋯ P n ≃ Q 2 Q 3 ⋯ Q m {\displaystyle P_{2}P_{3}\cdots P_{n}\simeq Q_{2}Q_{3}\cdots Q_{m}}
既約多項式

同様に、
既約多項式

P 2 | Q 2 ∨ P 2 | Q 3 ∨ ⋯ ∨ P 2 | Q m . {\displaystyle P_{2}\,|\,Q_{2}\vee P_{2}\,|\,Q_{3}\vee \cdots \vee P_{2}\,|\,Q_{m}.}
既約多項式

であり、 P 2 | Q 2 {\displaystyle P_{2}\,|\,Q_{2}} として一般性を失わず、 P 2 ≃ Q 2 . {\displaystyle P_{2}\simeq Q_{2}.} である。以下同様に P n ≃ Q n {\displaystyle P_{n}\simeq Q_{n}} までが得られる。
既約多項式

ところで定理 ii より | P 1 P 2 ⋯ P n | = | Q 1 Q 2 ⋯ Q m | ⟺ | P 1 | + ⋯ | P n | = | Q 1 | + ⋯ + | Q m | {\displaystyle |P_{1}P_{2}\cdots P_{n}|=|Q_{1}Q_{2}\cdots Q_{m}|\iff |P_{1}|+\cdots |P_{n}|=|Q_{1}|+\cdots +|Q_{m}|} となり、先ほどの議論から
既約多項式

| P 1 | = | Q 1 | , | P 2 | = | Q 2 | , ⋯ | P n | = | Q n | {\displaystyle |P_{1}|=|Q_{1}|,|P_{2}|=|Q_{2}|,\cdots |P_{n}|=|Q_{n}|} なので
既約多項式

| Q n + 1 | = ⋯ = | Q m | = 0. {\displaystyle |Q_{n+1}|=\cdots =|Q_{m}|=0.}
既約多項式

すなわち n = m {\displaystyle n=m} が得られ、また P 1 ≃ Q 1 , P 2 ≃ Q 2 , ⋯ , P n ≃ Q n {\displaystyle P_{1}\simeq Q_{1},P_{2}\simeq Q_{2},\cdots ,P_{n}\simeq Q_{n}} より、因数分解の一意性が得られた。
既約多項式

除法の原理から、係数が有理数であれば、有理数上で既約な多項式の積に分解される。このことは有理数に限らず、実数や複素数、および任意の代数体上で成り立つ。特に複素数体上では、代数学の基本定理より、任意の多項式が定数と1次式の積に一意的に分解される。
既約多項式

さらに、整数係数の多項式は整数係数の、有理数上既約な多項式の積に分解されるが、これは後に合同多項式の理論を用いて示す。