原始多項式とその積について

二つの原始多項式 $f(x)$ と $g(x)$ を $m$ 次と $n$ 次とする。

$f(x)=a_mx^m+a_{m-1}x^{m-1}+\cdots +a_1x+a_0$

$g(x)=b_nx^n+b_{n-1}x^{n-1}+\cdots +b_1x+b_0$

とおく。

積 $f(x)g(x)$ が原始多項式でないと仮定して矛盾を導く。このとき，$f(x)g(x)$ の全ての係数を割り切る素数が存在するのでそれを $p$ とおく(※)。

$f(x)$ が原始多項式なので $a_0,\:a_1,\cdots,\:a_m$ の中に $p$ の倍数でないものが存在する。その中で添字が最小なものを $a_M$ とおく。

同様に，$b_0,\:b_1,\cdots,\:b_n$ の中で $p$ の倍数でないもので添字が最小なものを $b_N$ とおく。

このとき，$a_0$ から $a_{M-1}$ ，$b_{0}$ から $b_{N-1}$ まではいずれも $p$ の倍数である（※※）。

ここで，$f(x)g(x)$ の $M+N$ 次の項の係数 $c_{M+N}$ は，

$c_{M+N}=\displaystyle\sum_{k}a_kb_{M+N-k}$

である。ただし，和は $0\leq k\leq m$ および $0\leq M+N-k\leq n$ を満たす $k$ について取る。

上の式には $a_Mb_N$ という項が現れるが，この項は $p$ の倍数ではない。一方，$a_Mb_N$ という項以外は（※※）より全て $p$ の倍数である。よって $c_{M+N}$ は $p$ の倍数ではない。これは（※）に矛盾。