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 を約分して既約分数にせよ。
実にシンプルな問題ですね。この問題に答えるには、まずユークリッドの互除法を使って 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 で互除法を双方向で使ってみる