連分数3：不定方程式 ax+by=1 への応用

はじめに

　この記事では 前回の記事 の続きとして連分数展開のベズーの等式$ax+by=1$への応用について簡単にまとめていきます。

連分数展開とユークリッドの互除法

　まず有理数の連分数展開とユークリッドの互除法との関係について紹介していきましょう。
　いま有理数$x=a/b\quad(b>0)$の連分数展開
$$\frac ab=[c_0;c_1,c_2,\ldots,c_N]$$
を求めるためには
\begin{align} \frac ab&=c_0+\frac{r_1}b&&(0\leq r_1< b)\\ \frac b{r_1}&=c_1+\frac{r_2}{r_1}&&(0\leq r_2< r_1)\\ \frac{r_1}{r_2}&=c_2+\frac{r_3}{r_2}&&(0\leq r_3< r_2)\\ &\ \ \vdots\\ \frac{r_{N-1}}{r_N}&=c_N \end{align}
という計算をしていくことになりますが、これは整数$a,b$に対するユークリッドの互除法
\begin{align} a&=c_0b+r_1\\ b&=c_1r_1+r_2\\ r_1&=c_2r_2+r_3\\ &\ \ \vdots\\ r_{N-1}&=c_Nr_N \end{align}
と全く同じ計算をしていることがわかります。
　また上の関係式を
$$\begin{pmatrix}r_{n-1}\\r_n\end{pmatrix} =\begin{pmatrix}c_nr_n+r_{n+1}\\r_n\end{pmatrix} =\begin{pmatrix}c_n&1\\1&0\end{pmatrix} \begin{pmatrix}r_n\\r_{n+1}\end{pmatrix}$$
と表すことで
$$\begin{pmatrix}a\\b\end{pmatrix} =\begin{pmatrix}c_0&1\\1&0\end{pmatrix} \begin{pmatrix}c_1&1\\1&0\end{pmatrix}\cdots \begin{pmatrix}c_n&1\\1&0\end{pmatrix} \begin{pmatrix}r_n\\r_{n+1}\end{pmatrix}$$
という式が成り立ちますが、この右辺に現れる行列は 第一回の記事 の命題4から収束分数
$$\frac{p_n}{q_n}=[c_0;\ c_1,\ c_2,\ \ldots,\ c_n]$$
を用いて
$$\begin{pmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{pmatrix} =\begin{pmatrix}c_0&1\\1&0\end{pmatrix} \begin{pmatrix}c_1&1\\1&0\end{pmatrix}\cdots \begin{pmatrix}c_n&1\\1&0\end{pmatrix}$$
と表せたので
$$\begin{pmatrix}a\\b\end{pmatrix} =\begin{pmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{pmatrix} \begin{pmatrix}r_n\\r_{n+1}\end{pmatrix} =\begin{pmatrix}p_N&p_{N-1}\\q_N&q_{N-1}\end{pmatrix} \begin{pmatrix}\gcd(a,b)\\0\end{pmatrix}$$
といった関係式が得られます。

不定方程式$ax+by=1$

　ところで$a,b$が互いに素であるとき$r_N=\gcd(a,b)=1$となるので
$$r_n=ax_n+by_n$$
なる整数$x_n,y_n$を$n=1,2,\ldots,N$について逐次求めたり
$$1=r_{n-1}x'_n+r_ny'_n$$
なる整数$x'_n,y'_n$を$n=N-1,\ldots,1,0$について逐次求めていくことで
$$1=ax+by$$
なる整数$(x,y)=(x_N,y_N)=(x'_0,y'_0)$を得ることができるのでした。
　しかしこんな面倒くさい計算をしなくても
$$\det\begin{pmatrix}p_n&p_{n-1}\\q_n&q_{n-1}\end{pmatrix} =p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}$$
に注意すると、上での議論から
$$\begin{pmatrix}1\\0\end{pmatrix} =(-1)^{N-1}\begin{pmatrix}q_{N-1}&-p_{N-1}\\-q_N&p_N\end{pmatrix} \begin{pmatrix}a\\b\end{pmatrix}$$
が成り立っていたので
$$(-1)^{N-1}=aq_{N-1}-bp_{N-1}$$
を得ることができます。

　特にこのようにして得られる解$x,y$は次のような最小性を持つことに注意しましょう。

　ちなみに
$$|aY-bX|=1$$
を満たすような整数$X,Y\ (Y\geq0)$は定理1のような$x,y$を用いて
\begin{align} (X,Y) ={}&(ak+x,bk+y)\quad(k=0,1,2,\ldots),\\ &(ak-x,bk-y)\quad(k=1,2,3,\ldots) \end{align}
と表せるもので尽くされるわけですが、それらに対応する連分数は
\begin{align} \frac{ak+x}{bk+y}&=[a_0;a_1,a_2,\ldots,a_N,k]\\ \frac{ak-x}{bk-y}&=[a_0;a_1,a_2,\ldots,a_N-1,1,k-1] \end{align}
と表せます(ただし$N\geq0$または$a_N\geq2$とした)。

部分分数分解への応用

　ちなみに連分数展開の考え方は一般に除法の原理を考えられる対象に適用することができます。
　特に上と同様の方法によって互いに素な多項式$f(x),g(x)$に対し
$$f(x)q(x)-g(x)p(x)=1$$
なる多項式$p(x),q(x)$を求めることができるので、これは
$$\frac1{f(x)g(x)}=\frac{q(x)}{g(x)}-\frac{p(x)}{f(x)}$$
なる部分分数分解を求めたいときなどに役立ちます。

　またこの手法で不定方程式が解けることの本質は
$$p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}\prod^n_{k=1}b_k$$
という等式にあったので、この$b_k$を上手く操作することで一般の方程式
$$f(x)q(x)-g(x)p(x)=h(x)$$
の解を求めるのにも応用でき、これによって
$$\frac{h(x)}{f(x)g(x)}=\frac{q(x)}{g(x)}-\frac{p(x)}{f(x)}$$
という部分分数分解を得ることができます。

　なお一般の連分数
$$\frac fg=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}{\atop{}+\cdots+{}}\frac{b_N}{a_N}$$
においては、例えば
$$\frac{x(x+1)}{x^2}=\dfrac x{x-1+\dfrac 1{x+1}}$$
のように収束分数の既約性が保証されるとは限りません。
　ただ上の方法に関しては連分数展開の計算において余程変なことをしなければ
\begin{align} \begin{pmatrix}f\\g\end{pmatrix} &=\begin{pmatrix}a_0&b_1\\1&0\end{pmatrix} \begin{pmatrix}a_1&b_2\\1&0\end{pmatrix}\cdots \begin{pmatrix}a_n&b_{n+1}\\1&0\end{pmatrix} \begin{pmatrix}r_n\\r_{n+1}\end{pmatrix}\\ &=\begin{pmatrix}a_0&b_1\\1&0\end{pmatrix} \begin{pmatrix}a_1&b_2\\1&0\end{pmatrix}\cdots \begin{pmatrix}a_{N-1}&b_N\\1&0\end{pmatrix} \begin{pmatrix}a_N&1\\1&0\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix} \end{align}
という関係式は成り立つはずなので、$p_N=f,\ q_N=g$は保証されます($p_{N-1},q_{N-1}$が互いに素とは限らない)。
　またこの方法によって得られる$p,q$は($\deg h<\deg fg$において)
$$\deg p<\deg f,\quad \deg q<\deg g$$
という最小性を持つことに注意しましょう。