Root One

数学中心のブログです。

不定方程式を連分数で解く

今回はもう一度不定方程式

 ax - by = 1

の解法について調べます。以前、合同式を用いた解法を紹介しましたが、今回は連分数を用いる解法を紹介します。

(連分数についての基礎は 情報系学習サイト の「数学→連分数」もご覧ください。)

ここでは略記法として

\begin{align} [a_0,a_1,a_2,\cdots,a_n] = a_0 + \cfrac{1}{a_1+\cfrac{1}{\lower{3pt}{ a_2 \, + } \lower{15pt} {\ddots+ \cfrac{1}{a_n} } }} \end{align}

を採用します。

1以上の有理数は、必ず a_k \in \mathbb{N} \,\,  (k=0,\cdots,n) として上の形に連分数展開できることが知られています。

連分数の展開方法は、

Step1. 整数部分と小数部分に分ける。

Step2. 小数部分を次のようにひっくり返す。

 \displaystyle \mbox{小数部分}= \cfrac{1}{\cfrac{1}{\text{小数部分}}}

をくりかえすだけです。(詳細は上記サイト参照.)

例1.

\begin{align} \frac{7}{5} &=\text{整数部分}+\text{小数部分}  \\ &= 1 + \left( \frac{7}{5}-1 \right)\\ &= 2 + \frac{2}{5} \\ &= 2 + \frac{\,\,\,1\,\,\,}{\cfrac{5}{2}} & (\text{ひっくりかえす})\\ &= 2 + \frac{1}{\text{整数部分}+\text{小数部分} } \\ &= 2 + \frac{1}{2 + \cfrac{1}{2}} \end{align}

例2.

 \displaystyle \frac{225}{157}=1+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{4+\cfrac{1}{5}}}}

連分数の性質

自然数a_kに対して

 \displaystyle \frac{p_k}{q_k} = [a_0,\cdots,a_k ]

とおくと、各kに対して

 \displaystyle | p_k q_{k+1} - p_{k+1} q_k |  =1 

が成立します。

例.

 \displaystyle \frac{p_0}{q_0} = 1 = \frac{1}{1}

 \displaystyle \frac{p_1}{q_1} = [1,2 = \frac{3}{2} ]

 \displaystyle \frac{p_2}{q_2} = [1,2,3 = \frac{10}{7} ]

 \displaystyle \frac{p_3}{q_3} = [1,2,3,4 = \frac{43}{30} ]

 \displaystyle \frac{p_4}{q_4} = [1,2,3,4,5 = \frac{225}{157}]

と計算し、これらを並べます。

 \displaystyle \frac{1}{1}  ,\frac{3}{2} , \frac{10}{7} ,\frac{43}{30}, \frac{225}{157}

ここで、隣り合う分数に注目して、

「(左)分子×(右)分母ー(右)分子×(左)分母」を行うと\pm1になります。

\begin{alignat}{2} & 1\times2 - 3\times1 &&= -1\\ &3\times 7 - 10 \times 2 &&= 1 \\ & 10\times 30 - 43 \times 7 &&= -1 \\ &43\times 157 - 30 \times 225 &&= 1 \end{alignat}

不定方程式への応用

上の性質を不定方程式に利用します。以前解いたセンター試験(2019)の問題を解いてみます。

問題(センター2019)

 49x-23y=1

解法.

まず係数49,23に注目して、分数49/23を考え、これを連分数展開します。

 \displaystyle \frac{49}{23}=2+\cfrac{1}{7+\cfrac{1}{1+\cfrac{1}{2}}}

略記法では

 \displaystyle \frac{49}{23} = [2,7,1,2]

となります。ここで、最後の2を除いた連分数を計算します。

 \displaystyle [2,7,1=2+\cfrac{1}{7+1} = \frac{17}{8} ]

これら二つの分数を並べると

 \displaystyle \frac{17}{8} , \frac{49}{23}

となりますが、ここで連分数の性質

「(左)分子×(右)分母ー(右)分子×(左)分母 = \pm1」に注目し、

左辺を実際に計算すると

 \displaystyle 17 \times 23 - 49\times 8 = -1

が得られます。これを少し変形すれば

 \displaystyle 49\times 8 - 23 \times 17 = 1

となるので、最初の不定方程式の解として

 \displaystyle x = 8, \quad y = 17

が得られます。