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

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

ユークリッドの互除法

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

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

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

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

スポンサーリンク

例題1:当てずっぽうのほうが楽な場合

(1) 7x+5y=1を満たす整数x,yの組を1組見つけよ。
(2) 83x+28y=1を満たす整数x,yの組を1組見つけよ。

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

答え(1) x=1のとき5y=-6となり不適。
x=2のとき5y=-13となり不適。
x=3のとき5y=-20となりy=-4。よってx=3,y=-4

(2)x=1のときy=-3なら右辺が-1になりそうなので
\( 83 \cdot 1 + 28 \cdot(-3)=-1\)

両辺に-1をかけると
\( 83 \cdot (-1) + 28 \cdot 3=1\)

よってx=-1,y=3

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

1234x+321y=1を満たす整数(x,y)の組を1組求めよ。

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

<ユークリッドの互除法の基本的な考え>
1. ax+byの「a」と「b」を書く。
2. a,bのうち,大きいほう÷小さいほうの余り△を求める
このときに a=○b+△ の形で書いておくと良い。
3. a,b,△のうち小さいもの2つを選ぶ。
4. その2つの中で大きいほう÷小さいほうの余り△を求める。
5. 3.で選んだの2つの数と△のうち小さいもの2つを選ぶ。
6. 4,5を繰り返し余りが1以下になれば終了する。

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

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以下になったので終了。最大公約数は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 とわかります。

これらを答案用紙に書くと非常に長くなりますし,結果がわかれば合ってることは1発でわかりますのでこれらの過程は「ユークリッドの互除法で求めよ」と指定されていない限り書く必要はないでしょう。だからこそあてずっぽうで見つけることも有効なのです。

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする