数論入門(山本)に沿って記述。理解に手間取った部分を補足して記録。
条件
\(p\) : 素数
\( f(X),g(X),h(X) \) : \(\mathbb{Z}\) 係数 monic 多項式
\( f(X) \equiv g(X) h(X) \, ( \mathrm{mod}\, p) \)
\( g(X) , h(X) \) は \(\mathrm{mod}\,p \) で互いに素
条件から \( g(X) , h(X) \) \(\mathbb{Z}\) 係数多項式としても互いに素。なぜなら、\( g(X) , h(X) \) が互いに素でなければ、\(\mathrm{mod}\,p\) でも互いに素でない。
結論
\( g_1(X)=g(X),\,h_1(X)=h(X) \) から始めて、以下の条件を満たすように monic 多項式 \(g_k(X),h_k(X) \) を順次構成できる。
\( g_k(X) \equiv g_{k-1}(X) \, (\mathrm{mod}\,p^{k-1}) \)
\( h_k(X) \equiv h_{k-1}(X) \, (\mathrm{mod}\,p^{k-1}) \)
\( f(X) \equiv g_k(X) h_k(X) \, (\mathrm{mod}\,p^{k}) \)
また、\(\mathrm{deg}\, g_k=\mathrm{deg}\, g\), \(\mathrm{deg}\, h_k=\mathrm{deg}\, h\) であり、更新によって次数は変わらない。monic 多項式なので最高次の係数は常に１。それ以外の係数について修正を繰り返す。
証明
\(k=1\) の場合は条件から良い。
\(k\) まで証明できたとする。
\(g_{k+1}(X)=g_k(X)+p^k\,G(X)\)
\(h_{k+1}(X)=h_k(X)+p^k\,H(X)\)
となる \( G,H \) を \( \mathrm{deg}\,G < \mathrm{deg}\,g_k,\,\mathrm{deg}\,H < \mathrm{deg}\,h_k \) となるように定めたい。こうすれば、\( \mathrm{deg}\,g_k,\,\mathrm{deg}\,h_k \) を変えることなく
\( g_{k+1}(X) \equiv g_k(X) \, (\mathrm{mod}\,p^k)\)
\( h_{k+1}(X) \equiv h_k(X) \, (\mathrm{mod}\,p^k)\)
とできる。
\( f(X) \equiv g_k(X) h_k(X) \, (\mathrm{mod}\,p^{k}) \) より \( f(X) \,-\, g_k(X) h_k(X) = p^k\, F(X) \) と書ける。\(f(X),\, g_k(X),\, h_k(X) \) は monic だから、左辺の最高次は消えて \( \mathrm{deg}\,F < \mathrm{deg}\, f = (\mathrm{deg}\,g)+(\mathrm{deg}\,h) \) となる。
\(\begin{eqnarray} && f(X) \,-\, g_{k+1}(X) h_{k+1}(X) \\
&=& f(X) \,-\, (g_k(X)+p^k\,G(X))(h_k(X)+p^k\,H(X)) \\
&=& \left( f(X) \,-\, g_k(X) h_k(X) \right) \,-\, p^{2k}\,G(X)H(X) \\
& & \quad \,-\, \, p^k \, \left( g_k(X) H(X) + h_k(X) G(X) \right) \\
&\equiv& p^k \, \left( F(X) \,-\, g_k(X) H(X) + h_k(X) G(X) \right) \quad (\mathrm{mod}\,p^{k+1})
\end{eqnarray} \)
これを \(\equiv 0 \, (\mathrm{mod}\,p^{k+1}) \) としたいから
\( F(X) \,\equiv \, g_k(X) H(X) + h_k(X) G(X) \,(\mathrm{mod}\,p)\)
となるような \(G(X), H(X) \) を与えたい。
\( g(X), h(X) \) は \(\mathrm{mod}\,p\) で互いに素だから、\( g(X) P(X) + h(X) Q(X) \equiv 1 \, (\mathrm{mod}\,p) \) となる \( P(X),Q(X) \) があるから、
\( g(X) F(X) P(X) + h(X) F(X) Q(X) \equiv F(X) \, (\mathrm{mod}\,p) \)
とできる。\(H(X)=F(X)P(X),\,G(X)=F(X)Q(X)\) を採用しても次数の条件を満たさないので、もう少し変形を要する。\(F(X)P(X)\) を \(h(X)\) で割り
\( F(X)P(X) = h(X) R(X) + S(X) \)
と表す。ここで \( \mathrm{deg}\,S < \mathrm{deg}\,h \) である。
\( g(X) S(X) + h(X) \left( g(X) R(X) + F(X) Q(X) \right) \equiv F(X) \, (\mathrm{mod}\,p) \)
\( H(X)=S(X),\,G(X)=g(X) R(X) + F(X) Q(X)\) とおく。\( \mathrm{deg}\,H < \mathrm{deg}\,h \) は既に見たので、\( \mathrm{deg}\,G < \mathrm{deg}\,g \) を示す。次数について次式が成り立つ。
\( \mathrm{deg}\,(gH+hG) = \mathrm{deg}\,F < \mathrm{deg}\,g+\mathrm{deg}\,h\)
\(\mathrm{deg} (gH) < \mathrm{deg}\,g+\mathrm{deg}h \) なので、\(\mathrm{deg}G \geq \mathrm{deg}\,g \) ならば \( \mathrm{deg}\,(gH+hG) \geq \mathrm{deg}\,g+\mathrm{deg} h \) となり矛盾。
