は法 で可逆である。したがって、ある
と
で
を満たすものが存在する。
多項式
を、次数が
未満で
と置いてもよいが、他のものを選んだ方が計算が簡単になることがある。例えば
で
の場合には、係数が区間 
に入る整数係数の多項式
を使って
と表せるようなものを取ることができるので、こう取ったほうがよい。
と
 に適用し、 と で
かつ
となるものを見つけることができる。この
 と は
かつ
となるものを取る。
このとき
である。実際、まず
の法
での次数が
の次数よりも小さくなるのは
のときだけである。
こうして、
を法とする合同を考えることにより次の式
が成り立つことがわかる。そして、
と置けば求めるものになっているので、存在が示せた。
一意性.
は前節と同じとする。 が
に適用して、多項式
と
であって
かつ
かつ次の式
を満たすものの存在がわかる。この多項式
と
は法
で一意に定まる。つまり、同じ条件を満たす組
が他にあったとすると、
が成り立つ。
を法とする合同は
を法とする合同を意味するので、
数学的帰納法を使って証明する。
 の場合は明らかである。
 の場合の一意性は証明されているものと仮定する。つまり、
と仮定する。仮定により
が成り立ち、これから
は法 で可逆なので、ある
と
が存在して
が成り立つ。これと帰納法の仮定から
が成り立つ。
法 で互いに素という仮定から、ある
が存在して
が成り立つ。帰納法の仮定をもう一度使うと
となる。したがって、次数が
未満の多項式が法
の場合だけなので、これから
が得られる。同様に
も
に含まれることが示せるので、これで一意性が証明できた。
での因数分解を法
 での計算だけで済んだが法
での計算が必要になるため、追加の計算コストがかかる。
どちらの方法でも大きな
 に対して法
まで持ち上げることができる。例えば
の場合に法
 回の反復計算が必要になるが、
 の性質、
使用する乗算アルゴリズム、
ハードウェアの特性などの状況に依存することを意味する。
ある正の整数 に対して因数分解
が存在し
が成り立つという意味で法
で互いに素だったとする。このとき、ある多項式
かつ
かつ
が成り立つ。さらに
と
 で
と置く。次の式
が、
と
で定めると
具体例.
多項式
を考えよう。
が
で既約であることは示せる。
は