有理数の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)$ という記号で表されます．