Python で互除法を双方向で使ってみる

7298 と 5963 の最大公約数はいくつ？

　中学数学のやり方は、まず2で割れるかどうかやってみて、割れなかったら3で割れるかどうかやってみて・・・こうやって順に共通因数を探しながら割っていく、というもの。
　　　　　　？　）7298　5963　
　　　　　　　　￣￣￣￣￣￣￣
　でも、どうでしょう、そのやり方で共通因数が見つかるでしょうか？　なにくわ（7298）ぬ顔でこんな数を出してみましたが、そのやり方ではたぶん苦労するでしょう。ごくろうさん（5963）なことです。
　ところで、高校数学では他のやり方を学びます。「ユークリッドの互除法」というものですが、それは実はプログラミングに最適なやり方なんです。つまり簡単にコードが書けて、しかも処理速度が速い。
　さて「ユークリッドの互除法」がどういうものかを説明するために、先に Python のコードを示します。

a=7298
b=5963
while b>0:
    r=a%b
    a=b
    b=r
print("最大公約数は ",a," です")

　シンプルでしょ。次にこのプログラムが何をしているかを具体的に見てみましょう。要は「a を b で割ったときの余り r を求める作業を、数字を下のようにずらしながら、割り切れるまで続ける」わけです。

7298 ÷ 5963 ＝ 1 … 1335
　　↙︎　　　　↙︎
5963 ÷ 1335 ＝ 4 … 623
　　↙︎　　　 ↙︎
1335 ÷ 623 ＝ 2 … 89
　　↙︎　　　↙︎
623 ÷ 89 ＝ 7 … 0

　余りが0になったときの「割られる数」、上の例でいうと「89」が求める最大公約数です。89は素数ですから、一番最初に書いたやり方で探そうとすると四苦八苦（89）するでしょう。
　そういえば、次のような問題が大学入試に出ていました。

約分せよ

148953／298767 を約分して既約分数にせよ。

　（横浜市立大学・医学部2017）

　実にシンプルな問題ですね。この問題に答えるには、まずユークリッドの互除法を使って 148953 と 298767 のGCDを求めることになります。
　手作業でやるなら（入試ですから当然手作業です）、

298767 ÷ 148953 ＝ 2 … 861
　　↙︎　　　　↙︎
148953 ÷ 861 = 173 … 0
よって GCDは 861
また 298767 ÷ 861 ＝ 347
よって 答えは 173／347。

　Python でやるなら、先ほどのプログラムをちょっとだけ書き換えて、
（※ ３行目と４行目で最初の分子・分母の値を保存している。最後の行を実行する時点では変数 a が最大公約数になっている。また、数値は元の 7298 と 5963 になっています）

a=7298
b=5963
aa=a
bb=b
while b>0:
    r=a%b
    a=b
    b=r
print(aa,"/",bb,"=",aa/a,"/",bb/a)

これで行けました。結果は、

7298 / 5963 = 82 / 67

と表示されました。

ユークリッドの互除法を逆順に利用する

　上の【問題】で約分が終わった時点で、分子 82 と分母 67 は互いに素になっています。そして２数が互いに素なら、次の方程式を満たす整数解が必ず存在します。

　　82x＋67y＝1

　このとき 82 と 67 は互いに素ですから、２数の最大公約数は 1 です。ユークリッドの互除法で確認してみましょう。

82 ÷ 67 ＝ 1 … 15　　⇔　  15 ＝ 82 − 67×1
　↙︎　　　↙︎
67 ÷ 15 ＝ 4 … 7　　 ⇔　　7 ＝ 67 − 15×4
　↙︎　　 ↙︎
15 ÷ 7 ＝ 2 … 1　　　⇔　　1 ＝ 15 − 7×2
　↙︎　　↙︎
7 ÷ 1 ＝ 7 … 0

　これを使って、方程式「82x＋67y＝1」の整数解が探せます。

1 ＝ 15 − 7×2
　　　　　↘︎
　＝ 15 − (67 − 15×4)×2
　＝ 15×9 − 67×2
　　　　↘︎
　＝ (82 − 67×1)×9 − 67×2
　＝ 82×9 − 67×11

　以上から、方程式「82x＋67y＝1」の整数解の１つ（特殊解）は (x , y) = (9 , −11) で、一般解は (x , y) = (9+67k , −11−82k) です。

　さて、たった今あげた「ユークリッドの互除法を逆順に利用する」件について、プログラムを組むとどうなるでしょうか？　手計算すると間違えそうで、だからこそコンピュータに早く・正確にやってもらいところです。
　とは言うものの、私は思いつかないのです。さて、どうしたものか？　この件を「Python プログラミング講座」の中で扱うには、どうすれば良いか？
　はい、ここで思いつきました。私が分からないままに、生徒たちに振っちゃえば良いんですね。単純な話でした。

「ユークリッドの互除法を逆に辿って方程式の整数解を求める」、その流れを Python プログラムで実現せよ。

　そこで良いアイデアが出てくれば、それで良し。出てこなくても、それで良し。それはそうと、この記事をお読みの方でアイデアをお持ちの方、どなたか教えていただけると幸いです。

◇　　　　　　◇　　　　　　◇

〜 Python で整数問題を腑に落とす 〜　
▷ Python で 0.1 を足し続けたらどうなるか？
▷ Python でＭ進数をＮ進数に変換する　　　
▷ Python で互除法を双方向で使ってみる