ユークリッドの互除法　大体は使わなくてもできますが・・・

上野竜生です。○x＋△y=1を満たす整数x,yの組を1組見つけるのがユークリッドの互除法の大きなメリットです。その方法を解説します。なお，見つけた後の応用分野については別の記事で行います。

ユークリッドの互除法とは本来はxとyの最大公約数を求めるアルゴリズムです。

xとyが互いに素（最大公約数が1）ならばax+by=1となる整数a,bが存在します。

そしてユークリッドの互除法をうまく応用すればaとbが互いに素のときax+by=1となるx,yを計算することができます。

ただし，少し複雑なのであてずっぽうで見つけるほうが楽なことが多いです。

例題１：当てずっぽうのほうが楽な場合

ユークリッドの互除法は万能なのでこの例題でも使えます。しかし，この程度なら適当に見つけるほうが楽でしょう。

例題２　あてずっぽうでは少ししんどい場合

例題１と比較すると数字が違うだけですが，あてずっぽうでは結構見つけにくいです。こういうときはユークリッドの互除法を使ってみましょう。

・・・と書かれてもわからないと思うので今回の例で計算してみます。

1.　「1234」「321」の最大公約数を求める。

2.　1234÷321=3あまり271　つまり，1234=3×321+271・・・①

3.　「1234」「321」「271」のうち小さいもの2つは「321」「271」

4.　321÷271=1あまり50　つまり，321=1×271+50・・・②

5.　「321」「271」「50」のうち小さいもの2つは「271」「50」

4.　271÷50=5あまり21　つまり271=5×50+21・・・③

5.　「271」「50」「21」のうち小さいもの2つは「50」「21」

4.　50÷21=2あまり8　つまり50=2×21+8・・・④

5.　「50」「21」「8」のうち小さいもの2つは「21」「8」

4.　21÷8=2あまり5　つまり21=2×8+5・・・⑤

5.　「21」「8」「5」のうち小さいもの2つは「8」「5」

4.　8÷5=1あまり3　つまり8=1×5+3・・・⑥

5.　「8」「5」「3」のうち小さいもの2つは「5」「3」

4.　5÷3=1あまり2　つまり5=1×3+2・・・⑦

5.　「5」「3」「2」のうち小さいもの2つは「3」「2」

4.　3÷2＝1あまり1　つまり3=1×2+1・・・⑧

6.　余りが1以下になったので終了。最大公約数は１

しかしこの問題では1234x+321y=1を満たす整数x,yを求めなくてはなりません。今度は⑧から順に復元していき1234×○＋321×△=1の形にもっていきます。

⑧：　3-2=1と変形でき，これで右辺を1にすることができました。以下では右辺はいじらずに左辺のみ変形していきます。

⑦：2=5-3と変形でき，これを上の式に代入すると3-(5-3)=1
つまり，-5+2×3=1と変形できます。

⑥：3=8-5と変形でき，これを上の式に代入すると-5+2×(8-5)=1
つまり，2×8+(-3)×5=1と変形できます。

⑤：5=21-2×8と変形でき，これを上の式に代入すると2×8+(-3)×(21-2×8)=1
つまり，(-3)×21+8×8=1と変形できます。

④：8=50-2×21と変形でき，上に代入すると(-3)×21+8×(50-2×21)=1
つまり，8×50+(-19)×21=1

③：21=271-5×50を上に代入すると8×50+(-19)×(271-5×50)=1
つまり，(-19)×271+103×50=1

②：50=321-271を上に代入すると(-19)×271+103×(321-271)=1
つまり，103×321+(-122)×271=1

①：271=1234-3×321を上に代入すると103×321+(-122)×(1234-3×321)=1
つまり，(-122)×1234+469×321=1

よって答えはx=-122，y=469　とわかります。