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