ユークリッドの互除法の基本

割り算からわかること

割り算の一般式は次の方法で表記できることがわかっている。

a=bq+r…(1-1)

a,qは整数(さらにqは式の商)、bは正の整数、rは整数とし

0<=r<bとする。

この式を変形して、次の形にするととあることがわかる。

a-bq=r…(1-2)

a ge bとする。

rは割り算でいうところの余りなので、r=0となるとa,bの最大公約数はbとなる。(qは商なので単なるbを倍加しているに過ぎない)このことを踏まえて、(1-2)式からわかることとしてa,bが持つ公約数eを持つとして、さらに式を変形していくと

e(a_{0}-b_{0}q)=er_{0}…(1-3)

a_{0},b_{0},r_{0}はeの商とする。

このことから、a,bの最大公約数においてもa,bは最大公約数で割り切れ、同時にrそれで割り切れるので

a,bの最大公約数はb,rの最大公約数と一致することがわかる。

2つの値の最大公約数の特定

先程の性質を利用することで、a,bb,rr,r_{1}→…→r_{n},0と繰り返すことでa,bの最大公約数r_{n}を特定することが可能である。例として1053と432の最大公約数の特定をしていこう。

1053-432q=r

1053=432q+rとなる。

この時rが最小の正の整数になるような組み合わせを考える。そうするとq=2,r=189となる。まだ余りが出るので、再度式を作ると

432=189*2-54となる。まだ余りがあるので

189=54*3-27

54=27*2-0

27が出た時点で余りが0になった。よって1053と432の最大公約数は27となる。

最大公約数の性質

先程求めた式を用いて、次に最大公約数が持つ性質についてみていく。

1053=432*2+189

432=189*2-54

189=54*3-27

54=27*2-0

これらの式を余り=の形にすると

189=1053-432*2…(3-1)

54=432-189*2…(3-2)

27=189-54*3…(3-3)

そして、3-3式に3-2式を代入し、その式に3-1式を代入してみると

27=1053*7+432*(-17)…(3-4)

となる。ここからわかることとして

27=1053*r+432*s

という感じで、適当な数字r,sで示すことができこの式を満たす1組が(r,s)=(7,-17)であることがわかった。

このことから、0でない2つの整数a,bの最大公約数をdとし、r,sを適当な整数とすると

d=a*r+b*s

で示すことができ、これを満たすr,sが存在することがわかる。

また、a,bが互いに素であると

1=a*r+b*s

となり、この時も式を満たすr,sが存在することもわかる。

参考書
数学読本1 著者:松坂和夫 出版社:岩波書店

コメント ※節度あるコメントをご協力をお願いたします。

タイトルとURLをコピーしました