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 を求める作業を、数字を下のようにずらしながら、割り切れるまで続ける」わけです。

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

約分せよ

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

　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 は互いに素になっています。そして２数が互いに素なら、次の方程式を満たす整数解が必ず存在します。

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

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

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

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

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

◇　　　　　　◇　　　　　　◇

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