現実と数学の区別が付かない

数学ネタのブログです

ヘンゼルの補題からニュートン・ピュイズーの定理へ

数学 ベキ級数

f(t,x)\in K[[t]][x] に対し，ヘンゼルの補題で f(0,x)\in K[x] の根 \alpha \in K が f(t,x) の根に持ち上がるための条件に \cfrac{\partial f}{\partial x}(0,\alpha)\neq 0 というものがありました。

egory-cat.hatenablog.com

この条件は外すことができません。

例として f(t,x)=x^n-t\in \mathbb{C}[[t]][x] の場合を考えてみましょう。 f(0,x)=x^n は n 重根 x=0 を持ちますが， f(t,x) は既約なので \mathbb{C}[[t]] に根は持ちません。

では f'(0,\alpha)= 0 となる f(0,x) の根からは何も情報が得られないのでしょうか？

再び f(t,x)=x^n-t\in \mathbb{C}[[t]][x] の場合を考えてみると， \mathbb{C}[[t^{\frac{1}{n}}]] にまで範囲を広げると， f(t,x) は n 個の根 \begin{align}t^{\frac{1}{n}},~ \zeta_nt^{\frac{1}{n}},~\dots,~ \zeta_n^{n-1}t^{\frac{1}{n}}\end{align}を持ちます (ただし \zeta_n は 1 の原始 n 乗根)。これらは t=0 を代入すると 0 になるので， f(0,x) の n 重根 x=0 が持ち上がったものと解釈できます。つまりこの例は，重根は \mathbb{C}[[t]] には持ち上がらないですが，少し大きくした \mathbb{C}[[t^{\frac{1}{n}}]] には持ち上がることを示唆しています。

今回紹介するのは次の定理です。

主定理
K を代数閉体とし，その標数を p\ge 0 とする (つまり p=0 または素数)。

f(t,x)=x^n+c_{n-1}(t)x^{n-1}+\cdots+c_1(t)x+c_0(t) \in K[[t]][x] を既約な多項式とする。

p=0 または \mathrm{gcd}(n,p)=1 のとき，ある \varphi(t)\in K[[ t]] が存在し， \varphi(t^\frac{1}{n}),~\varphi(\zeta_nt^\frac{1}{n}),~\dots,~\varphi(\zeta_n^{n-1}t^\frac{1}{n}) は f(t,x) の x の多項式としての相異なる n 個の根となる。

この定理の系として，次のニュートン・ピュイズーの定理が得られます。

ニュートン・ピュイズーの定理
K を標数 0 の代数閉体とする。このとき \displaystyle\bigcup_{n=1}^\infty K( (t^{\frac{1}{n}}) ) は代数閉体となる。

ここで，\displaystyle K( (t) )=K[[t]]\left[\frac{1}{t}\right]=\left\{\sum_{i=-N}^\infty c_it^i ~\middle|~ N\in \mathbb{N}, c_i \in K\right\} は K[[t]] の商体をあらわしています。\displaystyle\bigcup_{n=1}^\infty K( (t^{\frac{1}{n}}) ) の元のことをピュイズー級数といいます。

主張の形はちょっと違いますが，この定理のオリジナルの証明は本質的に1676年にニュートンがオルデンブルクに当てた手紙にあるそうです *1。

因数分解バージョンのヘンゼルの補題

ヘンゼルの補題には因数分解が持ち上がることを主張するバージョンもあり，こちらの方を単にヘンゼルの補題と呼ぶこともあります。

ヘンゼルの補題（因数分解バージョン）
f(t,x)=x^n+c_{n-1}(t)x^{n-1}+\cdots+c_1(t)x+c_0(t) \in K[[t]][x] とする。 f(0,x) が \begin{align}f(0,x)=g(x)h(x)\end{align}g(x),h(x) \in K[x],~\mathrm{gcd}(g(x),h(x))=1 と因数分解できるとき， g(t,x), h(t,x)\in K[[t]][x] で\begin{align}f(t,x)=g(t,x)h(t,x),~g(0,x)=g(x),~h(0,x)=h(x)\end{align} となるものが存在する。

この定理により， f(t,x) が既約のとき， f(0,x) は既約多項式のベキになっています。特に K が代数閉体のときは f(0,x)=(x-\alpha)^n という形になります。主定理は，この n重根 \alpha が n個の K[[t^{\frac{1}{n}}]] 内の根に持ち上がることを主張しています。

主定理の証明

記号は主定理の通りとします。この主定理はいくつか可換環論の有名な定理さえ認めてしまえば比較的簡単に証明することができます。というわけでこの証明はある程度可換環論を学んだ人向けです。

証明：
p=0 または \mathrm{gcd}(n,p)=1 なので， f(t,x) は x の分離多項式であることに注意する。

剰余環 A:=K[[t]][x]/(f(t,x)) の整閉包は，A の係数体 K 上のベキ級数環 K[[\tau]] と同型になる*2。 \iota:A\hookrightarrow K[[\tau]] を自然な埋め込みとする。\tau をうまく取り直すことで，\iota(t)=\tau^n としてよい*3。\iota(x)=\varphi(\tau) とすると，

0=\iota(f(t,x))=f(\iota(t),\iota(x))=f(\tau^n,\varphi(\tau))

となる。この等式の不定元 \tau に，形式的に \tau=\zeta_n^it^{\frac{1}{n}} (ただし 0\le i\le n-1，\zeta_n は 1 の原始n乗根) を代入することで \begin{align}f(t,\varphi(\zeta_n^it^{\frac{1}{n}}))=0\end{align}を得る。つまり \varphi(t^{\frac{1}{n}}),~\varphi(\zeta_nt^{\frac{1}{n}}),~\dots,~\varphi(\zeta_n^{n-1}t^{\frac{1}{n}}) は f(t,x) の x の多項式としての根となる。

\displaystyle g(t,x)=\prod_{i=0}^{n-1}\left(x-\varphi(\zeta_n^it^{\frac{1}{n}})\right) とおく。体の拡大 K( (t) )\subset K( (t^{\frac{1}{n}}) ) のガロワ群は \sigma: h(t^{\frac{1}{n}}) \mapsto h(\zeta_n t^{\frac{1}{n}}) で生成されるが， g_t(x) は \sigma で不変なので， g_t(x) \in K[[ t]][x] となる。よって f_t(x)=g_t(x) となり， \varphi(t^{\frac{1}{n}}),~\varphi(\zeta_nt^{\frac{1}{n}}),~\dots,~\varphi(\zeta_n^{n-1}t^{\frac{1}{n}}) は f(t,x) の x の多項式としての，相異なる n 個の根となる。（証明終）

ニュートン・ピュイズーの定理の証明

証明：
L:=\displaystyle\bigcup_{n=1}^\infty K( (t^{\frac{1}{n}}) ) とおく。 f(x)\in L[x]， \mathrm{deg}f(x)=d>0 とする。 f(x) が L に根を持つことを示せばよい。

ある n が存在して f(x) \in K( (t^{\frac{1}{n}}) )[x] となる。 T=t^{\frac{1}{n}} とおく。適当に K( (T) ) の元倍することで f(x) \in K[[T]][x] で，先頭項が T^m x^d であるとしてよい。 g(x)=T^{(d-1)m}f\left(\cfrac{x}{T^m}\right) とおくと，g(x) \in K[[T]][x] で先頭項は x^d となる。主定理により， g(x) の既約因子（その次数を r\le d とする ）の根となる \varphi(T^{\frac{1}{r}})\in K[[T^{\frac{1}{r}}]] が存在する。よって， f(x) は根 \cfrac{\varphi(T^{\frac{1}{r}})}{T^m} = t^{-\frac{m}{n}}\varphi(t^{\frac{1}{nr}}) \in L を持つ。（証明終）

*1:たぶんこれ Letter from Isaac Newton to Henry Oldenburg, dated 24 October 1676 (Normalized)。 手紙の後半に現在ではニュートン多角形と呼ばれるものの画 (Fig. 2) が出てきます。何が書いてあるかは読めませんが，このあたりで多項式のピュイズー級数根を求めているように見えます。

*2:これは，完備局所環についてのコーエンの構造定理，Krull-秋月の定理，完備局所環の有限拡大で整域なものは完備局所環であること，一次元の正規環は正則であることを用いて証明できます。

*3:重複度が双有理変換で変わらないことと，K[[\tau]] の可逆元が n 乗根を持つことからこのような \tau が取れます。

ベキ級数環における平方根の計算

数学 ベキ級数

一般化された二項定理によれば (1+t)^{\frac{1}{2}}=\sqrt{1+t} のマクローリン展開は\begin{align}
(1+t)^{\frac{1}{2}}=\sum_{k=0}^\infty \binom{\frac{1}{2}}{k}t^k,~~~\left|t\right|<1
\end{align}で与えられます。ここで \displaystyle \binom{\frac{1}{2}}{k} は一般化された二項係数 \begin{align}
\binom{\frac{1}{2}}{k}=\cfrac{\cfrac{1}{2} \left( \cfrac{1}{2}-1 \right)\left( \cfrac{1}{2}-2 \right)\cdots \left( \cfrac{1}{2}-k+1 \right)}{k!}
\end{align}です。

Wikipedia 二項定理 ニュートンの一般化された二項定理
calculus - Taylor series of $\sqrt{1+x}$ using sigma notation - Mathematics Stack Exchange

具体的に初めの方の項を計算してみると\begin{align}
\sqrt{1+t}=1+\cfrac{1}{2}t-\cfrac{1}{8}t^2+\cfrac{1}{16}t^3-\cfrac{5}{128}t^4+\cfrac{7}{256}t^5+\cdots
\end{align}となります。

今回はあえてヘンゼルの補題を使って正標数の体 \mathbb{F}_p=\mathbb{Z}/p\mathbb{Z} 上のベキ級数環での \sqrt{1+t} の計算をしてみます。

そして最後に x^3+x^2-y^2 の既約性（因数分解できるかどうか）について考えてみます。

\mathbb{Z}_p と \mathbb{K}[[t]]

ユークリッド整域の典型的な例として，有理整数環 \mathbb{Z} と体 K 上の多項式環 K[t] があります。

ユークリッド環 - Wikipedia

どちらもユークリッド除算と呼ばれる「割り算」ができ，ユークリッドの互除法により最大公約元の計算ができます。\mathbb{Z} は「数論的」な環で，K[t] は「幾何的」な環です。

前回の記事紹介した数論的な環である p進整数環 \mathbb{Z}_p に対応する幾何的な環が体上の形式冪級数環

\begin{align} K[[t]] :=\left\{\sum_{k=0}^\infty c_kt^k \middle| c_k\in K\right\} \end{align}

です。これは収束を考えない形式的な無限和からなる環です。和や積も形式的に定義できますが，桁の繰り上がりがない分，計算は \mathbb{Z}_p よりも分かりやすいです。

一般的に幾何学的な環の方が数論的な環よりも分かりやすい構造をしています。

例えば \mathbb{Z} の素イデアル全体がどうなっているかは整数論における究極的な大問題ですが， \mathbb{C}[t] の素イデアル全体は \{(0)\}\cup\{(t-a)\mid a\in \mathbb{C} \} と簡単にかけます。

\mathbb{Z}_p と K[[t]] はどちらも完備離散付値環と呼ばれる環です。 K[[t]] に対しても， \mathbb{Z}_p と同様にヘンゼルの補題が成り立ちます。

ヘンゼルの補題とニュートン法

K[[t]] でのヘンゼルの補題を書いておきましょう。\mathbb{Z}_p で \mathrm{mod}~p を考えることは， K[[t]] では t=0 を代入することに対応します。やはり幾何的な環の方が話は簡単です。

ヘンゼルの補題
f_t(x)\in K[[t]][x] ， f_t(x) の t に 0 を代入したものを f_0(x)\in K[x] とする。

f_0(\alpha)=0， f_0'(\alpha)\neq 0 となる \alpha \in K が存在するとき， a(t)\in K[[t]] で f_t(a(t))=0 かつ a(0)=\alpha となるものが存在する。

f_0(x) の体 K における根 \alpha が f_t(x) の K[[t]] における根 a(t) に持ち上がるという定理です。この持ち上がった根 a(t) はニュートン法で計算することができます。

x_k(t) \in K[[t]] を以下を満たすように帰納的に定めます。 ただし f'_t(x) は x による微分 f'_t(x)=\cfrac{\partial f_t(x)}{\partial x} を表しています。
\begin{align}
x_1(t)&\equiv \alpha \mod t\\
x_{k+1}(t)&\equiv x_k(t) -\cfrac{f_t(x_k(t))}{f_t'(x_k(t))} \mod t^{2^k}
\end{align}このとき， (x_k(t))_{k=1,2,3,\dots} は収束し， \displaystyle a(t)=\lim_{k\to \infty}x_k(t) とすると，これは f_t(a(t))=0 を満たし，任意の k に対して a(t) \equiv x_k(t) \mod t^{2^{k-1}} となります。

K[[t]] における 1+t の n乗根

体 K を有理数体 \mathbb{Q} または有限体 \mathbb{F}_p=\mathbb{Z}/p\mathbb{Z} (p：素数) とします。a(t)\in K[[ t]] で， a(t)^n=1+t となるものは存在するでしょうか？

そのような a(t) は x に関する多項式 f_t(x)=x^n-(1+t)\in K[[t]] [x] の根になるので，ヘンゼルの補題を使って見つけることができます。

まず，f_0(x)=x^n-1 は根 x=1 を持ちます。また，f'_0(1)=n は K=\mathbb{Q} または K=\mathbb{F}_p が \mathrm{gcd}(n,p)=1 を満たす体のときは 0 になりません。よって，ヘンゼルの補題により，次の系が得られます。

系（1+t の n乗根）
n を正整数とし，K=\mathbb{Q} または K=\mathbb{F}_p (\mathrm{gcd}(n,p)=1) とする。このとき， a(t)\in K[[t]] で， a(t)^n=1+t, a(0)=1 を満たすものが存在する。

特に n=2 ， p>2 のときは a(t)^2=1+t, a(0)=1 を満たす a(t)\in \mathbb{F}_p[[t]] が存在します。この a(t) のことを \sqrt{1+t} で表すことにしましょう。

ちなみに p=2 のときは，このような a(t) は存在しません。\displaystyle a(t)=\sum_{k=0}^\infty c_k t^k \in \mathbb{F}_p[[t]] の2乗は \displaystyle a(t)^2= \sum_{k=0}^\infty c_k t^{2k} となり，c_k をどう上手く定めても 1+t にはなりません。

\sqrt{1+t}\ \in \mathbb{F}_p[[t]] の具体的な形

ニュートン法を用いて \sqrt{1+t}\in \mathbb{F}_p[[t]] を p=3,5,7,11,13 の場合に具体的に計算した結果は以下のようになります．

p=3 のとき：\begin{align}\small 1+2t+t^{2}+t^{3}+2t^{4}+t^{5}+t^{9}+2t^{10}+t^{11}+t^{12}+2t^{13}+t^{14}+\cdots\end{align}p=5 のとき：\begin{align}\small
1+3t+3t^{2}+t^{3}+2t^{5}+t^{6}+t^{7}+2t^{8}+t^{10}+3t^{11}+3t^{12}+t^{13}+\cdots\end{align}p=7 のとき：\begin{align}\small 1+4t+6t^{2}+4t^{3}+t^{4}+3t^{7}+5t^{8}+4t^{9}+5t^{10}+3t^{11}+3t^{14}+5t^{15}+\cdots\end{align}p=11 のとき：\begin{align}\small
1+6t+4t^{2}+9t^{3}+4t^{4}+6t^{5}+t^{6}+5t^{11}+8t^{12}+9t^{13}+t^{14}+9t^{15}+\cdots\end{align}p=13 のとき：\begin{align}\small 1+7t+8t^{2}+9t^{3}+9t^{4}+8t^{5}+7t^{6}+t^{7}+6t^{13}+3t^{14}+9t^{15}+\cdots\end{align}これらは \displaystyle (1+t)^{\frac{1}{2}}=\sum_{k=0}^\infty \binom{\frac{1}{2}}{k}t^k の各係数を \mathrm{mod}~ p で計算したものと一致しています。

x^3+x^2-y^2 の既約性

x^3+x^2-y^2\in\mathbb{R}[x,y] は多項式としては既約ですが，ベキ級数としては因数分解できます。
\begin{align}
x^3+x^2-y^2&=x^2(1+x)-y^2=(x\sqrt{1+x})^2-y^2=(x\sqrt{1+x}+y)(x\sqrt{1+x}-y)\\
&=\left(\sum_{k=0}^\infty \binom{\frac{1}{2}}{k}x^{k+1} +y\right)\left(\sum_{k=0}^\infty \binom{\frac{1}{2}}{k}x^{k+1} -y\right)
\end{align}この意味は x^3+x^2-y^2=0 のグラフを描いてみると分かります。

x^3+x^2-y^2=0 のグラフは全体としては一本の繋がった曲線です。

f:id:egory_cat:20180815170530p:plain:w400

しかし，原点の近くだけの範囲で考えると x^3+x^2-y^2=0 は2本の曲線 x\sqrt{1+x}+y=0 と x\sqrt{1+x}-y=0 が交差したものになってります。

f:id:egory_cat:20180815174405p:plain:w400

x^3+x^2-y^2\in \mathbb{F}_p[x,y] も多項式としては既約ですが，p\neq 2 のときはベキ級数としては因数分解できます。

p=2 のときは，x^3+x^2-y^2=x^3+(x+y)^2 ななので， z=x, w=x+y と変数変換すると z^3+w^2 となり，これはベキ級数としても既約なので，x^3+x^2-y^2 はベキ級数としても既約になります。

有理数のp進数展開とヘンゼルの補題

数学 p進数

今回はヘンゼルの補題を使って次の問題を解いてみます．

1715x^3-3920x^2+2968x-745 を \mathbb{Z}[x] の範囲で因数分解せよ．

この式は3次式なので，因数分解できるなら nx+m （n, m\in \mathbb{Z}）の形の因子で n| 1715, m| 745 となるものがあるはずなので，全ての場合を試すことでこの問題は解くことはできます．しかしこの方法には 1715 と 745 の素因数分解が必要なのと，総当たりで確かめるというのがちょっとダサいですよね？*1

まずはp進整数環の定義から始めましょう．

p進整数環 \mathbb{Z}_p

素数 p を一つ固定します．形式的な無限和の集合\begin{align}\mathbb{Z}_p:=\left\{\sum_{i=0}^\infty c_ip^i ~\middle|~ c_i\in\mathbb{Z}, 0\le c_i\le p-1\right\}\end{align}を p進整数環と呼びます．\mathbb{Z}_p の元 \xi を \displaystyle \sum_{i=0}^\infty c_ip^i~ (0\le c_i\le p-1) の形に表すことを， \xi の p進数展開と呼ぶことにします. 和や積をp進数展開された整数と同じように形式的に定義すると，\mathbb{Z}_p は環になります．つまり，和と積は

\begin{align}
&\sum_{i=0}^\infty a_ip^i +\sum_{i=0}^\infty b_ip^i = \sum_{i=0}^\infty (a_i+b_i)p^i \\
&\left(\sum_{i=0}^\infty a_ip^i\right)\left(\sum_{i=0}^\infty b_ip^i\right) =\sum_{k=0}^\infty \sum_{i+j=k}(a_ib_j)p^k
\end{align}

と一旦計算します．そして (a_i+b_i) や \sum_{i+j=k}(a_ib_j) が p を超えるときは「繰り上がり」が起きますが，この繰り上がりを p のベキが小さい方から順に「無限回」計算することで，和や積の p進数展開を得ることができます．この「無限回の繰り上がり」は次に説明する 「極限」と「\mathrm{mod}~ p^k での計算」 によって正当化できます．

\mathbb{Z}_p での極限

a, b\in\mathbb{Z}_p の p進数展開 \displaystyle a=\sum_{i=0}^\infty a_ip^i, b=\sum_{i=0}^\infty b_ip^i を考えます．この a,b の展開が何桁目まで一致しているかを w_p(a,~b) で表すことにします．すなわち\begin{align}
w_p(a,~b)=\min\{i\mid a_i\neq b_i\}
\end{align}と定義します．ただし，a=b のときは w_p(a,~b)=\infty と約束します．w_p(a~,b) は「 a-b が pで何回割れるか」を測るものです．*2

\mathbb{Z}_p の数列 (x_k)_{k=1,2,3,\dots} が \xi \in \mathbb{Z}_p に収束するとは， \displaystyle\lim_{k\to \infty} w_p(\xi,~ x_k)=\infty が成り立つときを言います．k を限りなく大きくしていくと， x_k と \xi の p進数展開が一致している部分も限りなく大きくなっていく様子が想像できるでしょうか．

数列 (x_k)_{k=1,2,3,\dots} が収束することと \displaystyle\lim_{k\to \infty} w_p(x_{k+1},x_k)=\infty が成り立つことは同値になります.

\mathbb{Z}/p^k\mathbb{Z} での計算

c\in\mathbb{Z}_p のp進数展開 \displaystyle\sum_{i=0}^\infty c_ip^i (0\le c_i\le p-1 ) を途中で切った \displaystyle\sum_{i=0}^{k -1} c_ip^i までの部分が知りたい場合は\begin{align}\mathbb{Z}_p/p^k\mathbb{Z}_p=\mathbb{Z}/p^k\mathbb{Z}=\left\{\sum_{i=0}^{k -1} c_ip^i ~\middle|~ \forall i, 0\le c_i\le p-1\right\}\end{align}で計算すればよく，また，\displaystyle c=\lim_{k\to \infty} \sum_{i=0}^{k -1} c_ip^i なので， c のことを知りたければ「すべてのk」に対して c \mod p^k が分かっていればいいことになります．

\mathbb{Z}/p^k\mathbb{Z} における計算は合同式に慣れている人にとってはお馴染みのものでしょう．

mathtrain.jp

どんな \mathbb{Z}/p^k\mathbb{Z} の元も 0\le n\le p^k -1 なる n で表すことができ， n を p進数展開を計算するとで \displaystyle\sum_{i=0}^{k -1} c_ip^i という形に変形することができます.

n\in \mathbb{Z} が n\not\equiv 0 \mod p を満たすとき， nm\equiv 1 \mod p^k となる m\in \mathbb{Z} をユークリッドの互除法を用いて計算することができます．つまり n の乗法逆元の計算は可能で \cfrac{1}{n}\equiv m \mod p^k です.

\mathbb{Z}/p^k\mathbb{Z} における計算を経由することで， \displaystyle\sum_{i=0}^\infty c_ip^i ( c_i\in\mathbb{Z} ) の形のもの（c_i に関する条件を 0\le c_i\le p-1 から単に整数に緩めたもの）も \mathbb{Z}_p の元と見なすことができます ．

\displaystyle x_k= \sum_{i=0}^{k-1} d_ip^i ( 0\le d_i\le p-1) を，\displaystyle x_k\equiv \sum_{i=0}^{k-1} c_ip^i \mod p^k を満たすものとすると， (x_k)_{k=1,2,3,\dots} は収束する数列になります．その極限である \mathbb{Z}_p の元を \displaystyle\sum_{i=0}^\infty c_ip^i は表していると解釈します． \displaystyle\sum_{i=0}^\infty c_ip^i ( c_i\in\mathbb{Z}) の形のもの同士の和や積は
\begin{align}
&\sum_{i=0}^\infty a_ip^i +\sum_{i=0}^\infty b_ip^i = \sum_{i=0}^\infty (a_i+b_i)p^i \\
&\left(\sum_{i=0}^\infty a_ip^i\right)\left(\sum_{i=0}^\infty b_ip^i\right) =\sum_{k=0}^\infty \sum_{i+j=k}(a_ib_j)p^k
\end{align}
と計算することができます．

乗法逆元の計算

形式的な計算で
\begin{align}
&(p-1)+(p-1)p+(p-1)p^2+(p-1)p^3+\cdots \\
=&(p+p^2+p^3+\cdots)-(1+p+p^2+p^3+\cdots)=-1
\end{align}
であることが分かります．これはいわゆる「1の補数」というやつです．これを利用して \mathbb{Z}_p における -1 倍を計算することもできます． また，この式から\begin{align}\cfrac{1}{1-p}=1+p+p^2+p^3+\cdots\end{align}であることも分かります．これはべき級数展開 \cfrac{1}{1-x}=1+x+x^2+x^3+\cdots の類似です.

これらは \mathbb{Z}/p^k\mathbb{Z} における等式
\begin{align} &(p-1)+(p-1)p+(p-1)p^2+(p-1)p^3+\cdots +(p-1)p^{k-1} \equiv -1 \mod p^k\\ &\cfrac{1}{1-p}\equiv 1+p+p^2+p^3+\cdots +p^{k-1} \mod p^k \end{align}
の極限と解釈することもできます．

より一般に，任意の \xi\in \mathbb{Z}_p に対して
\begin{align}\cfrac{1}{1-p\xi}=1+p\xi+p^2\xi^2+p^3\xi^3+\cdots \end{align}
が成り立ちます．

\displaystyle \xi=\sum_{i=0}^\infty c_ip^i \in \mathbb{Z}_p (c_i\in \mathbb{Z}) が可逆である必要十分条件は c_0 \not\equiv 0 \mod p であることです．

実際， c_0 \not\equiv 0 \mod p のとき， c_0 \cdot m \equiv 1 \mod p となる 0\le m\le p-1 をとると， m\xi=1+p\zeta とある \zeta\in \mathbb{Z}_p を用いて書くことができます．よって， \xi の逆元が\begin{align}\cfrac{1}{\xi}=\cfrac{m}{m\xi}=\cfrac{m}{1+p\zeta}=m(1-p\zeta+p^2\zeta^2-p^3\zeta^3+\cdots)\end{align}と計算することができます.

一方で c_0 \equiv 0 \mod p のとき，\xi \equiv 0 \mod p なので，どんな \eta \in \mathbb{Z}_p に対しても \xi\eta\equiv 0 \mod p となります．1 \not\equiv 0 \mod p なので \xi\eta は 1 になりえません．よって \xi は可逆元ではありません．

有理数の p進数展開

実数を10進法で表示したとき，有理数であることと循環小数になることは同値でした．実はこの類似が p進数展開でも成り立ちます．

前節の乗法逆元の議論により，分母が p と互いに素な分数は，\mathbb{Z}_p の元として p進数展開を計算することができます．この p進数展開が循環することを示しましょう．

まずは正の有理数の場合を考えます．この場合は整数 \ell\ge0, m>n\ge 0, a\ge 0, \mathrm{gcd}(m,p)=1 によって p^{-a}\left(\ell+\cfrac{n}{m}\right) と表すことができます．p^{-a} の部分は桁のシフトなので， \ell+\cfrac{n}{m} の部分のp進数展開が分かれば十分です．

さて，\mathrm{gcd}(m,p)=1 なので p^r-1 \equiv 0 \mod m となる整数 r>0 が存在します ( r を p の \mod m での位数とすればよい)．

このとき， \cfrac{n}{m}(p^r-1) は 0 以上 p^r-1 以下の整数なので\begin{align}\cfrac{n(p^r-1)}{m}=\sum_{i=0}^{r-1} c_i p^i ~~(0\le c_i\le p-1)
\end{align}とp進数展開することができます．よって\begin{align}\cfrac{n}{m}=-\cfrac{n(p^r-1)}{m}\cfrac{1}{1-p^r}=(\sum_{i=0}^{r-1} -c_i p^i) (1+p^r+p^{2r}+p^{3r}+\cdots)\end{align}となります．係数が0以下になってますが，周期 r で循環していますね．これに 0=1+(p-1)+(p-1)p+(p-1)p^2+\cdots を足すことで， \cfrac{n}{m} の循環するp進数展開を得ることができます．さらにこれに \ell を p進数展開したもの（非負整数なので有限の長さ）を足すことで， \ell+\cfrac{n}{m} の循環するp進数展開が得られます．

負の有理数 -\left(\ell+\cfrac{n}{m}\right) の場合は， \ell+\cfrac{n}{m} の循環するp進数展開を -1 倍して，それに 0=1+(p-1)+(p-1)p+(p-1)p^2+\cdots を足すことで循環するp進数展開が得られます.

逆に， \displaystyle\ell + \sum_{k=0}^\infty (\sum_{i=0}^{r-1} c_i p^i) p^{rk} と循環しているとき，これは \ell+\cfrac{\displaystyle\sum_{i=0}^{r-1} c_i p^i}{1-p^r} という有理数になります．

つまり，\mathbb{Z}_p の元が有理数であることと，p進数展開が循環することは同値になります．

具体的な例を計算してみましょう． p=3 として \cfrac{63}{13}=4+\cfrac{11}{13} の 3進数展開を計算してみます． 3^3-1=26 \equiv 0 \mod 13 で， \cfrac{3^3-1}{13}=2 です．まずは \cfrac{11}{13} の 3進数展開を計算します．
\begin{align}
\cfrac{11}{13}&=-\cfrac{11(3^3-1)}{13}\cfrac{1}{1-3^3}=-(1+3+2\cdot 3^2)\cfrac{1}{1-3^3}\\
&=(-1-3-2\cdot 3^2)+(-3^3-3^4-2\cdot 3^5)+(-3^6-3^7-2\cdot 3^8)+\cdots
\end{align}
これに 0=1+2+2\cdot3+2\cdot 3^2+2\cdot 3^3+\dots を足すことで\begin{align}\cfrac{11}{13}=(2+3)+(3^3+3^4)+(3^6+3^7)+(3^9+3^{10})+\cdots
\end{align}が得られました．これに 4=1+3 を足して\begin{align}\cfrac{63}{13}= 3^2+(3^3+3^4)+(3^6+3^7)+(3^9+3^{10})+ \cdots=3^2+\sum_{i=0}^\infty (3^3+3^4)3^{3i}
\end{align}という，循環した3進数展開が得られました．逆にこの p進数展開から，\begin{align}3^2+\sum_{i=0}^\infty (3^3+3^4)3^{3i}=9+\cfrac{3^3+3^4}{1-3^3}=\cfrac{63}{13}
\end{align}と，元の有理数を復元することもできます．

初めの数桁だけ知りたい場合は \mathbb{Z}/p^k\mathbb{Z} での計算が使えます． \cfrac{1}{24576962} の 3進数展開の p^3 までの桁を求めてみましょう．24576962 \equiv 23 \mod 3^4, 23\times74 \equiv 1\mod 3^4 なので\begin{align}
\cfrac{1}{24576962}\equiv \cfrac{1}{23}\equiv 74=2+2\cdot 3^2+2\cdot 3^3 \mod 3^4.
\end{align}よって， \cfrac{1}{24576962} の 3進数展開は 2+2\cdot 3^2+2\cdot 3^3 +\cdots となります．

ヘンゼルの補題とニュートン法

さて，\mathbb{Z}_p を利用して多項式 f(x) \in \mathbb{Z}[x] の有理数根を見つける方法を考えてみましょう．もしも，f(x) の有理数根が存在した場合，その分母と互いに素な素数 p を取ると，有理数根は \mathbb{Z}_p の元と見なすことができます．つまり，その有理数根は f(x) の \mathbb{Z}_p における根にもなっています．

循環している p進数展開で表される \mathbb{Z}_p の元を有理数の形に戻すことも可能だったことを思い出してください．つまり， f(x) の有理数根を探したい場合は，適当な p に対して， f(x) の \mathbb{Z}_p での根で，循環するp進数展開をもつものを探せばいいことになります．

しかし f(x) の \mathbb{Z}_p での根を計算する方法なんてあるのでしょうか？実はそれを可能にしてくれるのがヘンゼルの補題とニュートン法です．

wagomu.hatenablog.com

ヘンゼルの補題
p を素数， f(x)\in \mathbb{Z}_p[x] とする． f(\alpha)=0， f'(\alpha)\neq 0 となる \alpha \in \mathbb{F}_p が存在するとき， a\in \mathbb{Z}_p で f(a)=0 かつ a\equiv \alpha\mod p となるものが存在する．

f(x) の \mathbb{F}_p における根 \alpha が \mathbb{Z}_p における根 a に持ち上がるという定理です．この持ち上がった根 a はニュートン法で計算することができます．

x_k \in \mathbb{Z}_p を以下を満たすように帰納的に定めます.
\begin{align}
x_1&\equiv \alpha \mod p\\
x_{k+1}&\equiv x_k -\cfrac{f(x_k)}{f'(x_k)} \mod p^{2^k}
\end{align}このとき， (x_k)_{k=1,2,3,\dots} は収束し， a=\lim_{k\to \infty}x_k とすると，これは f(a)=0 を満たし，任意の k に対して a\equiv x_k \mod p^{2^{k-1}} となります．k が一つ上がるごとに a と x_k が一致する桁数が２倍になっているのは，ニュートン法が「２次収束」するからです．この事は上に挙げたサイトのヘンゼルの補題の証明をもう少し精密に読むことで分かります．

1715x^3-3920x^2+2968x-745 の因数分解

f(x)=1715x^3-3920x^2+2968x-745\in \mathbb{Z}[x] の因数分解を考えましょう. \mathbb{F}_2[x] の中で考えると，\begin{align}f(x)=x^3+1=(x+1)(x^2+x+1)\end{align}となります．x^2+x+1 は \mathbb{F}_2[x] で既約です．f(x) の\mathbb{Z}[x] での因数分解を \mathrm{mod}~2 で考えると， \mathbb{F}_2[x] での分解になります．つまり， f(x) が可約だとすると，１次と２次の既約多項式の積になるはずです．さて\begin{align}
f(1)=0,~~ f'(1)=3\cdot 1=1\neq 0 ~~~~\mbox{in}~\mathbb{F}_2 \end{align}なので，ヘンゼルの補題より， a\in \mathbb{Z}_2 で f(a)=0, a\equiv 1\mod 2 となるものが存在します． f(x) が可約だと仮定すると，この a はf(x) １次の因子 nx+m からえられる有理数根 -\cfrac{m}{n} を 2 進数展開したものになり，循環しているはずです．

ニュートン法を使って x_k \mod 2^{2^{k -1}} を計算していきましょう． a=\displaystyle\lim_{k\to\infty} x_k が f(a)=0 を満たす \mathbb{Z}_2 の元です.

まず x_1=1 です．以下 x_k を \mathbb{Z}/2^{2^{k-1}} \mathbb{Z} 内で計算していきます.

x_2\mod 2^2 の計算：\begin{align}
x_2\equiv 1-\cfrac{f(1)}{f'(1)}
\equiv 1-\cfrac{6}{9}\equiv 1-\cfrac{2}{1}\equiv 1-2 \equiv -1\equiv 1+2 \mod 2^2\end{align} x_3\mod 2^4 の計算：\begin{align}
x_3\equiv 1+2-\cfrac{f(1+2)}{f'(1+2)}
\equiv (1+2)-\cfrac{112}{89}\equiv (1+2)-\cfrac{7\times 2^4}{89}\equiv 1+2 \mod 2^4\end{align} x_4\mod 2^8 の計算：
\begin{align}
x_4&\equiv 1+2-\cfrac{f(1+2)}{f'(1+2)}
\equiv (1+2)-\cfrac{240}{153}\equiv 1+2 +2^4\times 169\\
&\equiv 1+2+2^4+2^7 \mod 2^8
\end{align}

x_5\mod 2^{16} の計算：
\begin{align}
x_5&\equiv 1+2+2^4+2^7-\cfrac{f(1+2+2^4+2^7)}{f'(1+2+2^4+2^7)} \equiv (1+2+2^4+2^7)-\cfrac{64512}{59385}\\
&\equiv 1+2+2^4+2^7+2^{10}\times 38921 \equiv 1+2+2^4+2^7+2^{10}+2^{13} \mod 2^{16}
\end{align}

どうやら \displaystyle\lim_{k\to\infty} x_k=1+\sum_{i=0}^\infty 2^{3i+1} となっていそうだという予想が立ちます．これは 循環しているので有理数で，実際に計算してみると\begin{align}1+\sum_{i=0}^\infty 2^{3i+1} =1+\cfrac{2}{1-2^3}=1-\cfrac{2}{7}=\cfrac{5}{7}\end{align}となります．

もしも \displaystyle\lim_{k\to\infty} x_k=1+\sum_{i=0}^\infty 2^{3i+1} が正しいなら \cfrac{5}{7} は f(x) の根になっているはずです．

試しに f(x) に代入してみると f\left(\cfrac{5}{7}\right)=0 となることが分かります．f(x) が 7x-5 を因子に持つことが分かりました.

f(x) を 7x-5 で割ることで \begin{align}f(x)=(7x-5)(245x^2-385x+149)\end{align}を得ます. ２次の因子は \mathrm{mod}~ 2 で考えても既約だったので， \mathbb{Z}[x] でも既約です.

よってこれが f(x) の \mathbb{Z}[x] の範囲での因数分解になっています．

*1:RSA暗号が素因数分解の困難さを安全性の根拠にしているように，素因数分解というのは一般には難しい問題なので，それを使うアルゴリズムは「ダサい」のです．そういう意味で2次多項式をたすき掛けで因数分解する方法も「ダサい」と思います．アルゴリズムとしては，解の公式を用いる方法の方がはるかに真っ当です．

*2:この w_p はこの記事だけでの記号です．w_p(a,~b) は普通は v_p(a-b) という記号で表されます．