ユークリッドの互除法

前回は，不定方程式の整数解を求めることを考えました

その中でも，やはり

の形の不定方程式が一番面白い（と私は思うのです）
これを見ると，数列の漸化式 や 線形の微分方程式 など様々な問題が関連して想起されます

まぁ，それはさておき・・・
昨日の練習問題にあった \begin{equation} 131x + 91y = 1 \end{equation} はおできになりましたでしょうか？　解を１つ見つけさえすれば良い・・・と言っても，これはなかなか面倒です

解答には，ユークリッドを互除法を使って，などといい加減な書き方をしてしまいましたので，ここで，整数解の１つである \(x = -25\)，\(y = 36\) の見つけ方を復習しておきたいと思います

ユークリッドの互除法

まずは，ユークリッドの互除法を保証する，大事な命題の説明から・・・

\(a\) と \(b\) の最大公約数，\(b\) と \(r\) の最大公約数を，それぞれ \(m\) と \(m'\)，したがって \begin{equation} a = mk,\quad b = ml \end{equation}

（\(k\) と \(l\) は 互いに素 です）

とします \begin{equation} r = a - bq = mk - mlq = m(k - lq) \end{equation} となって，\(r\) は \(m\) で割り切れることが分かります

\(b\) も \(m\) で割り切れるので，\(m\) は \(b\) と \(r\) の公約数となり，したがって \(m' \geqq m\) です

今度は逆に，\(m \geqq m'\) を示します

\(m'\) が \(b\) と\(r\) の最大公約数ですから \begin{equation} b = m'k', \quad r = m'l'\end{equation}

（\(k'\) と \(l'\) は 互いに素 です）

とします \begin{equation} a = bq + r = m'k'q + m'l' = m'(k'q + l') \end{equation} となって，\(a\) は \(m'\) で割り切れることが分かります

\(b\) も \(m'\) で割り切れるので，\(m'\) は \(a\) と \(b\) の公約数となり，したがって \(m \geqq m'\) となります

以上から，\(m = m'\) です

このことにより，除数を余りで次々に割っていって，余りが \(0\) になったときの除数が，２つの整数の最大公約数であると言えることが分かります

２元１次の不定方式の整数解を１つ見つける

それでは　\(131x + 91y = 1\) について，整数解の１つを探し出しましょう

まず，\(131\) と \(91\) について，互いに素な数同士だから，余りが \(1\) になるまで割り算を繰り返します \begin{equation} \label{euclid} \begin{array}{lcc} 131 = 91\cdot 1 + 40 & \cdots & (8.1) \\ 91 = 40\cdot 2 + 11 & \cdots & (8.2) \\ 40 = 11\cdot 3 + 7 & \cdots & (8.3) \\ 11 = 7\cdot 1 + 4 & \cdots & (8.4) \\ 7 = 4\cdot 1 + 3 & \cdots & (8.5) \\ 4 = 3\cdot 1 + 1 & \cdots & (8.6) \\ \end{array}\end{equation}　ここまで来たら，\((\ref{euclid}.6)\) の式をホンの少し変形して \begin{equation} 4 + 3\cdot(-1) = 1 \end{equation} とします
ここに \((\ref{euclid}.5)\) の式をホンの少し変形した \(3 = 7 - 4\cdot 1\) を代入すると \begin{equation} \begin{array}{l} 4 + (7 - 4\cdot 1)\cdot(-1) = 1 \\ \mbox{∴}\quad 7\cdot(-1) + 4\cdot 2 = 1 \end{array}\end{equation} 以下この操作を繰り返します \begin{equation} \begin{array}{l} 7\cdot(-1) + (11 - 7\cdot 1)\cdot 2 = 1 \\ \mbox{∴}\quad 11\cdot 2 + 7\cdot (-3) = 1 \\ 11\cdot 2 + (40 - 11\cdot 3)\cdot (-3) = 1 \\ \mbox{∴}\quad 40\cdot (-3) + 11\cdot 11 = 1 \\ 40\cdot (-3) + (91 - 40\cdot 2)\cdot 11 = 1 \\ \mbox{∴}\quad 91\cdot 11 + 40\cdot (-25) = 1 \\ 91\cdot 11 + (131 - 91\cdot 1)\cdot (-25) = 1 \\ \mbox{∴}\quad 131\cdot(-25) + 91\cdot 36 = 1 \end{array} \end{equation} となって，最後の式は \((x,\ y) = (-25,\ 36)\) が \(131x + 91y = 1\) を満たしていることを表しています
ところが，できたことはできたのですが，なかなか疲れます

自動化の試み

怠け者は，楽をしようと工夫します!!

こういうとき，結構役に立つのが Excel などの表計算ソフトです
スマホでも表計算ソフトが使えるので，どんどん使ったらイイと思います。

上の図は，Excel で A1 に 131 を，B1 に 91 をそれぞれ入力して，８列目に

\(131\cdot (-25) + 91\cdot 36 = 1\)

に相当する数値を表示させています
各セルに入力されている式は，下のとおりです

A1	131
B1	91
C1	=QUOTIENT(A1,B1)
D1	=MOD(A1,B1)
A2	=B1
B2	=D1
C2	=QUOTIENT(A2,B2)
D2	=MOD(A2,B2)
３列目～６列目は２列目をコピー
※QUOTIENT(セル１，セル２) はセル１をセル２で割った商
※MOD(セル１，セル２) はセル１をセル２で割った余り

これで，余りが１になるまでの割り算ができました
問題は，その下の表です・・・どのような式を書けば宜しいのでしょうか？

上の割り算の式 (1)～(6) を上から順に \begin{equation}a_n = b_n\cdot q_n + r_n\ (n = 1,\ 2,\ \cdots ,\ 6)\end{equation} とおくと \begin{equation} a_{n + 1} = b_n, \quad b_{n + 1} = r_n \end{equation} が成り立っており，さらに， \begin{equation} \alpha_n\cdot a_n + \beta_n\cdot b_n = 1\end{equation} として，\(\alpha_6\cdot a_6 + \beta_6\cdot b_n = 1\) すなわち \(4\cdot 1 + 3\cdot(-1) = 1\) から順に \(\alpha_1\cdot a_1 + \beta_1\cdot b_1 = 1\) を求める操作を考えましょう \begin{equation} \alpha_n\cdot a_n + \beta_n\cdot b_n = 1\end{equation} に \begin{equation} a_n = b_{n - 1},\quad b_n = r_{n - 1} = a_{n - 1} - q_{n - 1}\cdot b_{n - 1} \end{equation} を代入して整理をすると \begin{equation} \beta_n\cdot a_{n - 1} + (\alpha_n - \beta_n\cdot q_{n - 1})\cdot b_{n - 1} = 1\end{equation} Excel の 第13列 と 第12列 に入る 数値・式 は次のとおりになります

A13	=A6
B13	1
C13	=B6
D13	=-C6
A12	=A5
B12	=D13
C12	=B5
D12	=B13-D13*C5

第12列を第11列から第8列までコピーすると，表が完成します

この表では自動で計算できるという状況にはなっていませんが，中心となるアルゴリズムについては，このように考えて宜しいというものになっています

\(a\) と \(b\) の値を入力すれば，１つの整数解が求められるという表にするためには，条件文を多少追加しなければなりません
興味のある人は作ってみてください
上のことが分かっていれば，それほど難しいことではありません

プログラミング

小学校でプログラミング教育が始まっています
折角，解を求めるアルゴリズムが理解できたのであれば，それをプログラミングとして実現してみたくなります

私自身は，本当に若いころ，多少カジッタ程度ですが，このサイトでは Javascript を用いたアプレットを利用するので，何十年ぶりに簡単なプログラミングを再経験することになっています

Scratch は小学生が利用していますし，高等学校の教科「情報」では Python を扱う学校もあるようです

算数・数学や理科などで学んだ内容を利用して，プログラミングすることは，各科目の学習内容の深化や定着に貢献します

一例として，不定方程式の整数解を求める簡単なアプレットを作成しましたので，載せておきます