ユーグリットの互除法 私は数学の教科担任から、ユーグリットの互除法の別解を聞きましたが、記憶があやふ

ユーグリットの互除法


私は数学の教科担任から、ユーグリットの互除法の別解を聞きましたが、記憶があやふやなので質問させていただきます。

先生が教えたのは、2つのパターンをかけて引いていくことです。(画像)

それで、真ん中のようになったのですが、それからがわかりません。

いちばんは先生に聞くのがいいのでしょうが、入試期間のため忙しそうで聞くことができません。よろしくお願いします

質問者からの補足コメント

• 見えますか…

  
    補足日時：2019/03/03 19:37

No.3 回答者： ありものがたり 回答日時： 2019/03/03 21:58

補足のほうが、前の写真より解像度低いんですが...

互除法というのは、xをyで割った余りをrとすると
x,yの最大公約数はy,rの最大公約数と同じ... ってのを
反復適用して、数を小さくしていって最大公約数を見つける
という技法です。

110x + 90y = 1970 を解こうというなら、それは
互除法そのものというより、その応用編で、
110, 90 の最大公約数を互除法で求めて
それが 1970 の約数であることを確認する過程で
110x + 90y = 1970 の一般解も得られてしまう
という話です。「拡張ユークリッド互除法」でgoogleすると
やり方が紹介されていますよ。

No.2 回答者： kairou 回答日時： 2019/03/03 21:09

下記を参考にして。

https://www.studyplus.jp/412

No.1 回答者： Hypnomatic 回答日時： 2019/03/03 20:09

ユークリッド互除法は２つの数値を棒のように見立てて、それぞれをある長さの単位で区分したときに、その１つの長さが最大公約するであるという理論です

WikipediaにイメージしやすいGif画像が載っているので、それを頭にイメージすると考えやすいでしょう。

https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC …

なお、添付の画像は小さくて見えませんでした。