初等整数論/多項式

多項式とは、
a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 {\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}
のことである。 x {\displaystyle x} のことを「変数」、 a k {\displaystyle a_{k}} を「係数」という。一般に係数は範囲が明確に示されることが多い。 係数が属すべき範囲が異なると、多項式の性質も変化する。例えば x 3 − 2 {\displaystyle x^{3}-2} は有理数上ではこれ以上分解することができないが、実数上では ( x − 2 3 ) ( x 2 + 2 3 x + 4 3 ) {\displaystyle (x-{\sqrt[{3}]{2}})(x^{2}+{\sqrt[{3}]{2}}x+{\sqrt[{3}]{4}})} と分解され、複素数上では ( x − 2 3 ) ( x − 2 3 ω ) ( x − 2 3 ω 2 ) , ω = ( − 1 + − 3 ) / 2 {\displaystyle (x-{\sqrt[{3}]{2}})(x-{\sqrt[{3}]{2}}\omega )(x-{\sqrt[{3}]{2}}\omega ^{2}),\omega =(-1+{\sqrt {-3}})/2} と分解される。 そこで、係数が属すべき範囲を一つ固定して、その上で議論する。そして基本的に係数が属すべき範囲は、体(その範囲内で0以外の数で割り算が可能な集合)とする。有理数や実数、複素数はこれにあたるが、整数全体の集合は、 1/2, 1/3, 3/2 のようなものを含まないので、この項での議論には適さない場合がある。 係数がどの範囲の数なのかに従って、「整数係数多項式」、「有理係数多項式」などという。また a n ≠ 0 {\displaystyle a_{n}\neq 0} のとき、この方程式を「 n {\displaystyle n} 次多項式」という。
さて、式は次の2つに分けることができる。
どの式もこの2つに分けられることが分かるだろう。前者を「( x , y , z ⋯ {\displaystyle x,y,z\cdots } に関する)恒等式」、後者を「方程式」という。恒等式の変数が明らかな場合は略される。
例
さて、多項式に関して整数の場合と同じように整除性について組み立てることができる。
今から一般に変数が1つの多項式を扱う。多項式は P ( x ) {\displaystyle P(x)} で表す。何が変数なのか明らかな場合は P {\displaystyle P} と省略して書く。
2つの多項式が多項式として等しいとは、その係数がすべて一致することをいう。値が等しい場合と紛らわしいので、 P ( x ) ≡ Q ( x ) {\displaystyle P(x)\equiv Q(x)} という記号をもって、両者が多項式として等しいことを表すことにする。また P ≢ Q {\displaystyle P\not \equiv Q} はそうでない、つまり一致しない係数が存在することをいう。 つまり P ( x ) ≡ Q ( x ) {\displaystyle P(x)\equiv Q(x)} とは P ( x ) − Q ( x ) {\displaystyle P(x)-Q(x)} の係数がすべて 0 であることを意味し、 P ≢ Q {\displaystyle P\not \equiv Q} は P ( x ) − Q ( x ) {\displaystyle P(x)-Q(x)} が 0 ではない多項式であることを意味する。
さて、整数と同様の公理を満たすことを確認しなければならない。
P ≡ Q {\displaystyle P\equiv Q} ならば、
などである。これらは簡単に示すことができる。ここでは乗法の公理 5 を多項式でも満たすことを示す。
その前にいくつか他の定理を準備する。
0 ではない多項式の次数、すなわち a n ≠ 0 {\displaystyle a_{n}\neq 0} となる最大の n {\displaystyle n} を | A | {\displaystyle |A|} と表すこととする。(普通は deg  A {\displaystyle \deg A} と書くがここでは省略のためこう書くことにする)
定理 i | A | > | B | {\displaystyle |A|>|B|} のとき、 | A + B | = | A | . {\displaystyle |A+B|=|A|.}
A = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 , B = b m x m + b m − 1 x m − 1 + ⋯ + b 1 x + b 0 ( a n , b m ≠ 0 ) {\displaystyle A=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0},\ B=b_{m}x^{m}+b_{m-1}x^{m-1}+\cdots +b_{1}x+b_{0}\ \ (a_{n},b_{m}\,\neq 0)} とするとき、
| A | > | B | ⟺ n > m {\displaystyle |A|>|B|\iff n>m} なので、
A + B = a n x n + a n − 1 x n − 1 + ⋯ + ( a m + b m ) x m + ( a m − 1 + b m − 1 ) x m − 1 + ⋯ + ( a 1 + b 1 ) x + ( a 0 + b 0 ) {\displaystyle A+B=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +(a_{m}+b_{m})x^{m}+(a_{m-1}+b_{m-1})x^{m-1}+\cdots +(a_{1}+b_{1})x+(a_{0}+b_{0})}
よって | A + B | = | A | . {\displaystyle |A+B|=|A|.}
定理 ii A ( x ) ≢ 0 , B ( x ) ≢ 0 {\displaystyle A(x)\not \equiv 0,\ B(x)\not \equiv 0} ならば、 | A B | = | A | + | B | . {\displaystyle |AB|=|A|+|B|.} 特に A ( x ) B ( x ) ≢ 0. {\displaystyle A(x)B(x)\not \equiv 0.}
B = b m x m + b m − 1 x m − 1 + ⋯ + b 1 x + b 0 ( b m ≠ 0 ) {\displaystyle B=b_{m}x^{m}+b_{m-1}x^{m-1}+\cdots +b_{1}x+b_{0}\ \ (b_{m}\neq 0)} とする。
| A | = 0 {\displaystyle |A|=0} のとき、すなわち A ( x ) = a {\displaystyle A(x)=a} のとき、
A B = a b m x m + a b m − 1 x m − 1 + ⋯ + a b 1 x + a b 0 {\displaystyle AB=ab_{m}x^{m}+ab_{m-1}x^{m-1}+\cdots +ab_{1}x+ab_{0}} であり、また a b m ≠ 0 {\displaystyle ab_{m}\neq 0} より、 | A B | = | B | = | A | + | B | . {\displaystyle |AB|=|B|=|A|+|B|.}
次に | A | < n {\displaystyle |A|<n} のとき正しいとする。
A ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 , A ′ ( x ) = A ( x ) − a n x n ( a n ≠ 0 ) {\displaystyle A(x)=a_{n}x^{n}+a_{n-1}x_{n-1}+\cdots +a_{1}x+a_{0},\ A'(x)=A(x)-a_{n}x^{n}\ \ \ (a_{n}\neq 0)} とする。
A B = a n x n B + A ′ B . {\displaystyle AB=a_{n}x^{n}B+A'B.} このとき | A ′ | < n {\displaystyle |A'|<n} より | A ′ B | = | A ′ | + | B | < n + m . {\displaystyle |A'B|=|A'|+|B|<n+m.}
a n x n B = a n b m x n + m + a n b m − 1 x n + m − 1 + ⋯ + a n b 1 x n + 1 + b 0 x n , a n b m ≠ 0 {\displaystyle a_{n}x^{n}B=a_{n}b_{m}x^{n+m}+a_{n}b_{m-1}x^{n+m-1}+\cdots +a_{n}b_{1}x^{n+1}+b_{0}x^{n},\ \ a_{n}b_{m}\neq 0} より、 | a n x n B | = n + m . {\displaystyle |a_{n}x^{n}B|=n+m.}
したがって定理 i より、 | A B | = | a n x n B + A ′ B | = n + m . {\displaystyle |AB|=|a_{n}x^{n}B+A'B|=n+m.}
以上より累積帰納法より、正しいことが証明される。
さていよいよ次の定理を証明する。
定理 iii A ( x ) C ( x ) ≡ B ( x ) C ( x ) ∧ C ( x ) ≢ 0 ⇒ A ( x ) ≡ B ( x ) . {\displaystyle A(x)C(x)\equiv B(x)C(x)\wedge C(x)\not \equiv 0\Rightarrow A(x)\equiv B(x).}
A ( x ) C ( x ) ≡ B ( x ) C ( x ) {\displaystyle A(x)C(x)\equiv B(x)C(x)} であるとき C ( x ) ( A ( x ) − B ( x ) ) ≡ 0 {\displaystyle C(x)(A(x)-B(x))\equiv 0} である。ここで A ( x ) ≢ B ( x ) {\displaystyle A(x)\not \equiv B(x)} であったとすると、 C ( x ) ≢ 0 {\displaystyle C(x)\not \equiv 0} と仮定しているから定理 ii より C ( x ) ( A ( x ) − B ( x ) ) ≢ 0 {\displaystyle C(x)(A(x)-B(x))\not \equiv 0} となり矛盾。
よって定理は背理法によって証明される。
定義
P ( x ) ≡ Q ( x ) R ( x ) {\displaystyle P(x)\equiv Q(x)R(x)} が成り立つとき、 P {\displaystyle P} は Q , R {\displaystyle Q,R} を因数に持つ、 P {\displaystyle P} は Q , R {\displaystyle Q,R} で割り切れるという。記号で Q | P {\displaystyle Q\,|\,P} と書くことにする。
R | P 1 , P 2 , ⋯ , P n {\displaystyle R\,|\,P_{1},P_{2},\cdots ,P_{n}} のとき、 R | P 1 Q 1 + P 2 Q 2 + ⋯ P n Q n {\displaystyle R\,|\,P_{1}Q_{1}+P_{2}Q_{2}+\cdots P_{n}Q_{n}}
証明 仮定より P 1 = R S 1 , P 2 = R S 2 , ⋯ , P n = R S n {\displaystyle P_{1}=RS_{1},\,P_{2}=RS_{2},\cdots ,P_{n}=RS_{n}} とおく。すると、
P 1 Q 1 + P 2 Q 2 + ⋯ P n Q n = R S 1 Q 1 + R S 2 Q 2 + ⋯ + R S n Q n = R ( S 1 Q 1 + S 2 Q 2 + ⋯ + S n Q n ) {\displaystyle {\begin{aligned}P_{1}Q_{1}+P_{2}Q_{2}+\cdots P_{n}Q_{n}&=RS_{1}Q_{1}+RS_{2}Q_{2}+\cdots +RS_{n}Q_{n}\\&=R(S_{1}Q_{1}+S_{2}Q_{2}+\cdots +S_{n}Q_{n})\end{aligned}}}
よって定理は証明される。
さて、整数の整除についての根幹を成す定理は定理 1.2 であるが、幸いにも多項式にも同様の定理が成り立つことが言える。
任意の多項式 A , B ( B ( x ) ≢ 0 ) {\displaystyle A,B\ (B(x)\not \equiv 0)} について、
A = B Q + R {\displaystyle A=BQ+R} で、 R {\displaystyle R} の次数が B {\displaystyle B} よりも小さいような組 ( Q , R ) {\displaystyle (Q,R)} がただ一つ存在する。また、 A , B {\displaystyle A,B} の係数が有理数であれば Q , R {\displaystyle Q,R} の係数も有理数であり、 A , B {\displaystyle A,B} の係数が整数で B {\displaystyle B} の最高次の係数が1ならば Q , R {\displaystyle Q,R} の係数も整数である。
また、このとき x = α {\displaystyle x=\alpha } を B ( x ) = 0 {\displaystyle B(x)=0} の解とすると A ( α ) = R ( α ) . {\displaystyle A(\alpha )=R(\alpha ).}
証明 | A | < | B | {\displaystyle |A|<|B|} のとき、
Q = 0 , R = A {\displaystyle Q=0,R=A} とすれば定理の主張を満たす。
| A | = | B | {\displaystyle |A|=|B|} のとき、
A = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 , B = b n x n + b n − 1 x n − 1 + ⋯ + b 1 x + b 0 {\displaystyle A=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0},\ B=b_{n}x^{n}+b_{n-1}x^{n-1}+\cdots +b_{1}x+b_{0}} とする。このとき、
b n ≠ 0 {\displaystyle b_{n}\neq 0} であることから、 Q = a n b n B {\displaystyle Q={\frac {a_{n}}{b_{n}}}B} とおくと、
B Q = a n x n + ( a n b n − 1 b n ) x n − 1 + ⋯ + ( a n b 1 b n ) x + ( a n b 0 b n ) . {\displaystyle BQ=a_{n}x^{n}+\left({\frac {a_{n}b_{n-1}}{b_{n}}}\right)x^{n-1}+\cdots +\left({\frac {a_{n}b_{1}}{b_{n}}}\right)x+\left({\frac {a_{n}b_{0}}{b_{n}}}\right).} したがって、
A − B Q = ( a n − 1 − a n b n − 1 b n ) x n − 1 + ⋯ + ( a 1 − a n b 1 b n ) x + ( a 0 − a n b 0 b n ) {\displaystyle A-BQ=\left(a_{n-1}-{\frac {a_{n}b_{n-1}}{b_{n}}}\right)x^{n-1}+\cdots +\left(a_{1}-{\frac {a_{n}b_{1}}{b_{n}}}\right)x+\left(a_{0}-{\frac {a_{n}b_{0}}{b_{n}}}\right)} となる。
R = A − B Q {\displaystyle R=A-BQ} とおけば、この式は A = B Q + R {\displaystyle A=BQ+R} と恒等式になり、また明らかに | R | < | A | . {\displaystyle |R|<|A|.} よって定理の主張を満たす。
次に | A | > | B | {\displaystyle |A|>|B|} のときであるが、これには数学的帰納法を用いる。
| A | = α , | B | = β {\displaystyle |A|=\alpha ,\,|B|=\beta } とし、 α − β = n > 0 {\displaystyle \alpha -\beta =n>0} なので、 n {\displaystyle n} に対して数学的帰納法を用いる。
A = a α x α + a α − 1 x α − 1 + ⋯ + a 1 x + a 0 , B = b β x β + b β − 1 x β − 1 + ⋯ + b 1 x + b 0 {\displaystyle A=a_{\alpha }x^{\alpha }+a_{\alpha -1}x^{\alpha -1}+\cdots +a_{1}x+a_{0},\ B=b_{\beta }x^{\beta }+b_{\beta -1}x^{\beta -1}+\cdots +b_{1}x+b_{0}}
とおく。
(i) n = 1 {\displaystyle n=1} のとき
B = b α − 1 x α − 1 + b α − 2 x α − 2 + ⋯ + b 1 x + b 0 {\displaystyle B=b_{\alpha -1}x^{\alpha -1}+b_{\alpha -2}x^{\alpha -2}+\cdots +b_{1}x+b_{0}} となる。
このとき、 ( a α b α − 1 x ) B = a α x α + ( a α b α − 1 b α − 1 ) x α − 1 + ⋯ + ( a α b 1 b 1 ) x 2 + ( a α b 0 b α − 1 ) x {\displaystyle \left({\frac {a_{\alpha }}{b_{\alpha -1}}}x\right)B=a_{\alpha }x^{\alpha }+\left({\frac {a_{\alpha }b_{\alpha -1}}{b_{\alpha -1}}}\right)x^{\alpha -1}+\cdots +\left({\frac {a_{\alpha }b_{1}}{b_{1}}}\right)x^{2}+\left({\frac {a_{\alpha }b_{0}}{b_{\alpha -1}}}\right)x}
したがって、 Q = a α b α − 1 x {\displaystyle Q={\frac {a_{\alpha }}{b_{\alpha -1}}}x} とおけば、
R = A − B Q = ( a α − 1 − a α b α − 1 b α − 1 ) x α − 1 + ⋯ + ( a 2 − a 2 b 1 b 1 ) x 2 + ( a 1 a α b 0 b α − 1 ) x + a 0 {\displaystyle R=A-BQ=\left(a_{\alpha -1}-{\frac {a_{\alpha }b_{\alpha -1}}{b_{\alpha -1}}}\right)x^{\alpha -1}+\cdots +\left(a_{2}-{\frac {a_{2}b_{1}}{b_{1}}}\right)x^{2}+\left(a_{1}{\frac {a_{\alpha }b_{0}}{b_{\alpha -1}}}\right)x+a_{0}}
となり、よって定理の主張を満たす。
(ii) n = k {\displaystyle n=k} のとき正しいとする。
さて、 A = a α x α + a α − 1 x α − 1 + ⋯ + a 1 x + a 0 , B = b β x β + b β − 1 x β − 1 + ⋯ + b 1 x + b 0 {\displaystyle A=a_{\alpha }x^{\alpha }+a_{\alpha -1}x^{\alpha -1}+\cdots +a_{1}x+a_{0},\ B=b_{\beta }x^{\beta }+b_{\beta -1}x^{\beta -1}+\cdots +b_{1}x+b_{0}} とおいて、
α − β = k + 1 {\displaystyle \alpha -\beta =k+1} だとする。 A {\displaystyle A} の最高次を取った多項式
A ′ = a α − 1 x α − 1 + ⋯ + a 1 x + a 0 {\displaystyle A'=a_{\alpha -1}x^{\alpha -1}+\cdots +a_{1}x+a_{0}} について、 | A ′ | − | B | = k {\displaystyle |A'|-|B|=k} より、帰納法の仮定から
A ′ = B Q + R ( | R | < | B | ) ⋯ ( 1 ) {\displaystyle A'=BQ+R\ \ (|R|<|B|)\cdots (1)} と書ける。
( a α b β x α − β ) B = a α x α + ( b β − 1 a α b β ) x α − 1 + ⋯ + ( b 1 a α b β ) x α − β + 1 + ( b 0 a α b β ) x α − β {\displaystyle \left({\frac {a_{\alpha }}{b_{\beta }}}x^{\alpha -\beta }\right)B=a_{\alpha }x^{\alpha }+\left({\frac {b_{\beta -1}a_{\alpha }}{b_{\beta }}}\right)x^{\alpha -1}+\cdots +\left({\frac {b_{1}a_{\alpha }}{b_{\beta }}}\right)x^{\alpha -\beta +1}+\left({\frac {b_{0}a_{\alpha }}{b_{\beta }}}\right)x^{\alpha -\beta }}
したがって、 S = a α b β x α − β , C = ( b β − 1 a α b β ) x α − 1 + ⋯ + ( b 1 a α b β ) x α − β + 1 + ( b 0 a α b β ) x α − β {\displaystyle S={\frac {a_{\alpha }}{b_{\beta }}}x^{\alpha -\beta },\ C=\left({\frac {b_{\beta -1}a_{\alpha }}{b_{\beta }}}\right)x^{\alpha -1}+\cdots +\left({\frac {b_{1}a_{\alpha }}{b_{\beta }}}\right)x^{\alpha -\beta +1}+\left({\frac {b_{0}a_{\alpha }}{b_{\beta }}}\right)x^{\alpha -\beta }} とおけばこの式は
S B = a α x α + C {\displaystyle SB=a_{\alpha }x^{\alpha }+C} と書ける。ところで a α x α = A − A ′ {\displaystyle a_{\alpha }x^{\alpha }=A-A'} より、
(1) より S B = ( A − A ′ ) + C ⟺ A = B ( S + Q ) + ( R − C ) ⋯ ( 2 ) {\displaystyle SB=(A-A')+C\iff A=B(S+Q)+(R-C)\cdots (2)}
ここで | C | − | B | = α − 1 − β = k {\displaystyle |C|-|B|=\alpha -1-\beta =k} より帰納法の仮定から C = B Q ′ + R ′ ( | R ′ | < | B | ) {\displaystyle C=BQ'+R'\ \ (|R'|<|B|)} と書ける。
∴ ( 2 ) ⟺ A = B ( S + Q ) + ( R − B Q ′ − R ′ ) ⟺ A = B ( S + Q − Q ′ ) + ( R − R ′ ) {\displaystyle \therefore (2)\iff A=B(S+Q)+(R-BQ'-R')\iff A=B(S+Q-Q')+(R-R')}
ここで | R | < | B | , | R ′ | < | B | {\displaystyle |R|<|B|,\ |R'|<|B|} より | R − R ′ | < | B | . {\displaystyle |R-R'|<|B|.}
したがって、 k + 1 {\displaystyle k+1} のときも定理の主張を満たす。
(i) (ii) より数学的帰納法から証明される。またその構成から、係数に関する主張も従う。
次は除法が一意であることを証明する。仮にある多項式 A {\displaystyle A} が B {\displaystyle B} で割ったときに、二通りに書けたとする。
A = B Q + R ( | R | < | B | ) A = B Q ′ + R ′ ( | R ′ | < | B | ) {\displaystyle {\begin{aligned}A&=BQ+R\ \ &(|R|<|B|)\\A&=BQ'+R'\ \ &(|R'|<|B|)\\\end{aligned}}}
すると B ( Q − Q ′ ) + ( R − R ′ ) = 0 ⟺ B ( Q − Q ′ ) = R ′ − R {\displaystyle B(Q-Q')+(R-R')=0\iff B(Q-Q')=R'-R} となる。すなわち R ′ − R {\displaystyle R'-R} は B {\displaystyle B} を因数に持つことになる。しかし仮定より | R | − | R ′ | < | B | {\displaystyle |R|-|R'|<|B|} なので、 B {\displaystyle B} に 0以外の0次以上の多項式をかけても次数が B {\displaystyle B} より小さくなることはない。したがって Q − Q ′ = 0 {\displaystyle Q-Q'=0} とならざるをえない。これによって R ′ − R = 0 {\displaystyle R'-R=0} が導かれ、結局 Q = Q ′ , R = R ′ {\displaystyle Q=Q',\,R=R'} となり、ただ一通りにしか書けないことが証明される。
さて、長くなってしまったが、これで我々の必要としていた定理が導かれた。
P ( x ) {\displaystyle P(x)} を ( x − a ) {\displaystyle (x-a)} という多項式で割ったときの式を、定理 1.2 に従って
P ( x ) = ( x − a ) Q ( x ) + b {\displaystyle P(x)=(x-a)Q(x)+b} とする。余りが0次なのは、1次式で割っているからである。
定理 2 より b = P ( a ) {\displaystyle b=P(a)} である。実際、 P ( a ) = ( a − a ) Q ( x ) + b = b {\displaystyle P(a)=(a-a)Q(x)+b=b} となる。つまり、余りの値が分かるのである。これより、次の定理が従う。
定理
P ( x ) {\displaystyle P(x)} を ( x − a ) {\displaystyle (x-a)} で割ったときの余りは P ( a ) {\displaystyle P(a)}
特に P ( a ) = 0 {\displaystyle P(a)=0} のとき、 P ( x ) = ( x − a ) Q ( x ) {\displaystyle P(x)=(x-a)Q(x)} と書ける。つまり、 P ( x ) {\displaystyle P(x)} は ( x − a ) {\displaystyle (x-a)} を因数に持つ。この定理は剰余の定理の特別な場合だが、重要であるため「因数定理」という名前が付いている。
P ( a ) = 0 {\displaystyle P(a)=0} となる a {\displaystyle a} のことを、多項式 P {\displaystyle P} の零点という。
多項式に関する定理で重要な定理に次のものがある。
定理
多項式 A ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 {\displaystyle A(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}} について、
A ( x ) = 0 {\displaystyle A(x)=0} が恒等式 ⟺ A ( x ) ≡ 0 ⟺ a n = 0 ∧ a n − 1 = 0 ∧ ⋯ ∧ a 1 = 0 ∧ a 0 = 0. {\displaystyle \iff A(x)\equiv 0\iff a_{n}=0\wedge a_{n-1}=0\wedge \cdots \wedge a_{1}=0\wedge a_{0}=0.}
証明 ⇐ {\displaystyle \Leftarrow } は自明だろう。 ⇒ {\displaystyle \Rightarrow } を n {\displaystyle n} に関する数学的帰納法で証明する。
まず、0次式の場合は自明である。1次式の場合は、 A ( x ) = a x + b {\displaystyle A(x)=ax+b} に α ≠ β {\displaystyle \alpha \neq \beta } の2つを代入して
a α + b = 0 , a β + b = 0 {\displaystyle a\alpha +b=0,\ a\beta +b=0} したがって a ( α − β ) = 0. {\displaystyle a(\alpha -\beta )=0.}
ところで α − β ≠ 0 {\displaystyle \alpha -\beta \neq 0} より a = 0 {\displaystyle a=0} よって b = 0. {\displaystyle b=0.}
次に、 n − 1 {\displaystyle n-1} 次式でこの定理が正しいと仮定し、 n {\displaystyle n} 次式でも正しいことを証明する。 A ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 {\displaystyle A(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}} とする。このとき A ( x ) = 0 {\displaystyle A(x)=0} は恒等式だから異なる n + 1 {\displaystyle n+1} 個の値 x 0 , x 1 , ⋯ , x n {\displaystyle x_{0},x_{1},\cdots ,x_{n}} を代入しても A ( x 0 ) = ⋯ = A ( x n ) = 0. {\displaystyle A(x_{0})=\cdots =A(x_{n})=0.}
因数定理より、 A ( x ) = ( x − x 0 ) Q ( x ) {\displaystyle A(x)=(x-x_{0})Q(x)} と書ける。このとき、 Q ( x ) {\displaystyle Q(x)} の最高次の係数は a n {\displaystyle a_{n}} であることは簡単に分かる。また、 A ( x 1 ) = ( x 1 − x 0 ) Q ( x 1 ) = 0 {\displaystyle A(x_{1})=(x_{1}-x_{0})Q(x_{1})=0} なのだが、 x 1 − x 0 ≠ 0 {\displaystyle x_{1}-x_{0}\neq 0} より Q ( x 1 ) = 0. {\displaystyle Q(x_{1})=0.} 再び因数定理より、
Q ( x ) = ( x − x 1 ) Q 1 ( x ) {\displaystyle Q(x)=(x-x_{1})Q_{1}(x)} と書ける。このときの Q 1 {\displaystyle Q_{1}} の最高次の係数も a n {\displaystyle a_{n}} であることが簡単に分かる。これを代入して A ( x ) = ( x − x 0 ) ( x − x 1 ) Q 1 ( x ) . {\displaystyle A(x)=(x-x_{0})(x-x_{1})Q_{1}(x).} これを繰り返せば
A ( x ) = a n ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x n − 1 ) . {\displaystyle A(x)=a_{n}(x-x_{0})(x-x_{1})\cdots (x-x_{n-1}).}
A ( x n ) = a n ( x n − x 0 ) ( x n − x 1 ) ⋯ ( x n − x n − 1 ) = 0 {\displaystyle A(x_{n})=a_{n}(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})=0} だが、 x n − x 0 ≠ 0 , x n − x 1 ≠ 0 ⋯ x n − x n − 1 ≠ 0 {\displaystyle x_{n}-x_{0}\neq 0,x_{n}-x_{1}\neq 0\cdots x_{n}-x_{n-1}\neq 0} より
a n = 0 {\displaystyle a_{n}=0} となる。したがって A ( x ) = a n − 1 x n − 1 + a n − 2 x n − 2 + ⋯ + a 1 x + a 0 {\displaystyle A(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots +a_{1}x+a_{0}} となる。
以上より数学的帰納法によって証明される。
P ( x ) {\displaystyle P(x)} を多項式とし、 α {\displaystyle \alpha } を方程式 P ( x ) = 0 {\displaystyle P(x)=0} の解とする。因数定理より、これは P ( x ) {\displaystyle P(x)} が x − α {\displaystyle x-\alpha } を因数に持つことと同値である。 α {\displaystyle \alpha } が重解あるいは重根であるとは、 P ( x ) {\displaystyle P(x)} が ( x − α ) 2 {\displaystyle (x-\alpha )^{2}} を因数に持つことである。同様に α {\displaystyle \alpha } が n {\displaystyle n} 重解あるいは n {\displaystyle n} 重根であるとは、 P ( x ) {\displaystyle P(x)} が ( x − α ) n {\displaystyle (x-\alpha )^{n}} を因数に持つことである。
さて、多項式 P ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 0 {\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0}} に対し、微分 d d x P ( x ) {\displaystyle {\frac {d}{dx}}P(x)} あるいは P ′ ( x ) {\displaystyle P'(x)} を
により定める(これは微分積分学における多項式関数の微分と同様である。ただしここでは、関数ではなく多項式そのものに対する演算として微分を定める。ここでの議論には極限に関する議論を要しない点に注意)。
すると、明らかに次の2つの公式が成り立つ。また逆に次の2つの公式が成り立つように d d x P ( x ) {\displaystyle {\frac {d}{dx}}P(x)} を定めれば、一般の多項式について上記の公式が成り立つ。
さらに、
が成り立つ。 実際、 P ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 0 , Q ( x ) = x m {\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},Q(x)=x^{m}} のとき
であるから、一般の Q ( x ) = b m x m + b m − 1 x m − 1 + ⋯ + b 0 {\displaystyle Q(x)=b_{m}x^{m}+b_{m-1}x^{m-1}+\cdots +b_{0}} についても
が成り立つ。
P ( x ) {\displaystyle P(x)} が x = α {\displaystyle x=\alpha } を解に持つとし P ( x ) = ( x − α ) Q ( x ) {\displaystyle P(x)=(x-\alpha )Q(x)} とおくと
より P ′ ( α ) = Q ( α ) {\displaystyle P'(\alpha )=Q(\alpha )} となる。ここで P ( x ) {\displaystyle P(x)} が x = α {\displaystyle x=\alpha } を重解に持つとは、 Q ( α ) = 0 {\displaystyle Q(\alpha )=0} と同義であるから次のことがわかる。
P ( x ) {\displaystyle P(x)} が x = α {\displaystyle x=\alpha } を重解に持つための必要十分条件は P ( α ) = P ′ ( α ) = 0 {\displaystyle P(\alpha )=P'(\alpha )=0} が成り立つことである。
また、より一般に、一般に P ( X ) {\displaystyle P(X)} が Q ( X ) {\displaystyle Q(X)} で割り切れるとき P ( X ) = Q ( X ) P 1 ( X ) {\displaystyle P(X)=Q(X)P_{1}(X)} とおくと
であるから Q ( X ) | P 1 ( X ) {\displaystyle Q(X)|P_{1}(X)} ならば Q ( X ) | P ′ ( X ) {\displaystyle Q(X)|P'(X)} である。よって次のことがわかる。
P ( x ) {\displaystyle P(x)} が Q ( x ) 2 {\displaystyle Q(x)^{2}} を因数に持つならば P ( X ) , P ′ ( X ) {\displaystyle P(X),P'(X)} が共に Q ( X ) {\displaystyle Q(X)} を因数に持つ。
ここでは逆は必ずしも成り立たない。たとえば X 4 , ( X 4 ) ′ = 4 X 3 {\displaystyle X^{4},(X^{4})'=4X^{3}} は共に X 3 {\displaystyle X^{3}} で割り切れるが X 4 {\displaystyle X^{4}} は X 6 {\displaystyle X^{6}} で割り切れないのは明らかである。

多項式 A , B , ⋯ {\displaystyle A,B,\cdots } について、それら全ての因数である多項式を「公倍多項式」という。0次の多項式(定数項)は自明に約数である。
また多項式 A , B , ⋯ {\displaystyle A,B,\cdots } 全てを因数に持つ多項式を「公約多項式」という。
多項式に関する公約・公倍は整数のときと同じ定義・記号を使う。最大公約・最小公倍多項式は次数が最大・小のものをいう。ただし 0 は最小公倍多項式に含めないものとする。このとき定数項に注意しなければならないが、ここでは公約・公倍多項式の最高次が 1 になるようにする、また多項式に定数をかけることで同じになるものは同じとみなす、というルールを取り決めることにする。(最高次の係数が 1 な多項式を「モニック」という。)
適当な定数 c {\displaystyle c} が存在して A = c B {\displaystyle A=cB} と書けるとき、これを A ≃ B {\displaystyle A\simeq B} と表すこととする。
さて、多項式 A , B {\displaystyle A,B} の最大公約多項式が 1 {\displaystyle 1} であるとき、この2つの多項式は「互いに素」である、という。
整数の場合と同様に、多項式 A , B {\displaystyle A,B} の最大公約多項式を gcd ( A , B ) {\displaystyle \gcd(A,B)} , 最小公倍多項式を LCM ( A , B ) {\displaystyle {\textrm {LCM}}(A,B)} とかく。 たとえば、方程式 P ( x ) = 0 {\displaystyle P(x)=0} が重解 x = α {\displaystyle x=\alpha } を持つならば、 x − α {\displaystyle x-\alpha } は P , P ′ {\displaystyle P,P'} の公約多項式だから gcd ( P , P ′ ) > 1 {\displaystyle \gcd(P,P')>1} でなければならない(複素数上ならば代数学の基本定理より逆が成り立つが、他の体で考えているときは逆は成り立つとは限らない。公約多項式が解を持つとは限らないからである)。
ここでも整数の時と同じように理論を組み立てられる。
2つ以上の多項式の公倍多項式は最小公倍多項式を因数に持つ。
証明 多項式を A , B , ⋯ {\displaystyle A,B,\cdots } とおく。これらを全てかけたもの A B ⋯ {\displaystyle AB\cdots } は公倍多項式なので、公倍多項式は存在する。そのうちで最小のものも存在するはずである。
さて、最小公倍多項式を L {\displaystyle L} とし、 M {\displaystyle M} を任意の公倍多項式とおく。除法の原理に基づいて
M = L Q + R ( | R | < | L | ) {\displaystyle M=LQ+R\ \ (|R|<|L|)} とおく。このとき、 R = M − L Q . {\displaystyle R=M-LQ.}
M , L {\displaystyle M,L} ともに A , B , ⋯ {\displaystyle A,B,\cdots } を因数に持つ。したがって定理 1 より R {\displaystyle R} も A , B , ⋯ {\displaystyle A,B,\cdots } を因数に持つ。ゆえに R {\displaystyle R} は公倍多項式となるが、 R ≠ 0 {\displaystyle R\neq 0} とすると L {\displaystyle L} の最小性に反する。したがって R = 0. {\displaystyle R=0.}
したがって、 M = L Q . {\displaystyle M=LQ.} よって定理は証明された。
2つ以上の多項式の最大公約多項式は公約多項式を因数に持つ。
証明 多項式を A , B , ⋯ {\displaystyle A,B,\cdots } とおく。1 は明らかに公約多項式なので、公約多項式は存在し、そのうち最大のものが存在するはずである。
さて、最大公約多項式を M {\displaystyle M} とし、 D {\displaystyle D} を任意の公約多項式とおく。 L = l c m ( M , D ) {\displaystyle L=lcm(M,D)} とする。
仮定より A {\displaystyle A} は M , D {\displaystyle M,D} の公倍多項式。よって、定理 3 より A {\displaystyle A} は L {\displaystyle L} を因数に持つ。どうようの理由で B , ⋯ {\displaystyle B,\cdots } も L {\displaystyle L} を因数に持つ。したがって L {\displaystyle L} は A , B , ⋯ {\displaystyle A,B,\cdots } の公約多項式。 M {\displaystyle M} は最大のものなので | L | ≦ | M | ⋯ ( 1 ) . {\displaystyle |L|\leqq |M|\cdots (1).}
ところで L {\displaystyle L} は M {\displaystyle M} を因数に持つので L = M K . {\displaystyle L=MK.}
定理 ii より | L | = | M | + | K | . {\displaystyle |L|=|M|+|K|.}
これと (1) によって | L | = | M | {\displaystyle |L|=|M|} となり、 K {\displaystyle K} は定数項。ゆえに L {\displaystyle L} は D {\displaystyle D} を因数に持つので L = k M = D E {\displaystyle L=kM=DE} より M = 1 k D E . {\displaystyle M={\frac {1}{k}}DE.}
したがって M {\displaystyle M} は D {\displaystyle D} を因数に持つことが分かった。
gcd ( A , B ) = G , LCM ( A , B ) = L {\displaystyle \gcd(A,B)=G,\,{\textrm {LCM}}(A,B)=L} とすれば A B ≃ G L . {\displaystyle AB\simeq GL.}
証明 仮定より L = A ′ B = A B ′ {\displaystyle L=A'B=AB'} とおける。 A B {\displaystyle AB} は公倍多項式なので、定理 3 より A B = D L ⋯ ( 1 ) {\displaystyle AB=DL\cdots (1)} とおける。
先ほどの式を代入して A B = D A ′ B = D A B ′ ⇒ A = D A ′ , B = D B ′ . {\displaystyle AB=DA'B=DAB'\Rightarrow A=DA',\,B=DB'.} よって、 D {\displaystyle D} は A , B {\displaystyle A,B} の公約多項式。定理 4 より G = D E ⋯ ( 2 ) {\displaystyle G=DE\cdots (2)} とおく。このときもちろん E ( x ) ≠ 0. {\displaystyle E(x)\neq 0.}
G | A , B ⟺ D E | D A ′ , D B ′ {\displaystyle G\,|\,A,B\iff DE\,|\,DA',DB'} となる。ここで、 D A ′ = D E A ′′ , D B ′ = D E B ′′ {\displaystyle DA'=DEA'',DB'=DEB''} とおくと定理 iii より A ′ = E A ′′ , B ′ = E B ′′ {\displaystyle A'=EA'',B'=EB''} であるから最初の式に代入すると
L = E A ′′ B = E B ′′ A {\displaystyle L=EA''B=EB''A} を得る。ここで | E | > 0 {\displaystyle |E|>0} とすれば、 A ′′ B = B ′′ A {\displaystyle A''B=B''A} が公倍多項式となり、 L {\displaystyle L} の最小性に反する。従って E {\displaystyle E} は定数項となり、 E = e {\displaystyle E=e} とおけば (2) より G = e D . {\displaystyle G=eD.} (1) より
A B = 1 e D L ⇒ A B ≃ D L . {\displaystyle AB={\frac {1}{e}}DL\Rightarrow AB\simeq DL.}
A , B {\displaystyle A,B} が互いに素であるとき、 A | B C ⇒ A | C {\displaystyle A\,|\,BC\Rightarrow A\,|\,C}
証明 gcd ( A , B ) = 1 {\displaystyle \gcd(A,B)=1} なので定理 5 より LCM [ A , B ] = A B . {\displaystyle {\textrm {LCM}}[A,B]=AB.}
仮定より B C {\displaystyle BC} は A , B {\displaystyle A,B} の公倍多項式。定理 3 より LCM [ A , B ] | B C ⟺ A B | B C . {\displaystyle {\textrm {LCM}}[A,B]\,|\,BC\iff AB\,|\,BC.} よって定理 iii より A | C . {\displaystyle A\,|\,C.}
これにより、多項式においても、整除性に関して、整数の場合と同様の基本的事実が成り立つことがわかった。これを用いて、多項式上で、因数分解の一意性が成り立つことを次に見る。
なお、定理 4 の帰結として次の定理が成り立つ。
P ( x ) {\displaystyle P(x)} が平方因数 Q ( x ) 2 {\displaystyle Q(x)^{2}} を持つならば Q ( x ) {\displaystyle Q(x)} は gcd ( P , P ′ ) {\displaystyle \gcd(P,P')} の因数である。特に方程式 P ( x ) = 0 {\displaystyle P(x)=0} が重解 x = α {\displaystyle x=\alpha } を持つならば、 x − α {\displaystyle x-\alpha } は gcd ( P , P ′ ) {\displaystyle \gcd(P,P')} の因数である。
注意 : 係数比較の定理は、有理数や実数上、あるいは代数体上では正しいが、有限体上ではかならずしも正しくない。すなわち有限体上では値がつねに 0 であるが、多項式として 0 ではないものが存在する。そのため、一般に多項式と、多項式の表す関数(多項式関数)は区別しなければならない。