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

割り算からわかること

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

…(1-1)

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

とする。

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

…(1-2)

とする。

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

…(1-3)

はeの商とする。

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

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

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

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

となる。

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

となる。まだ余りがあるので

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

最大公約数の性質

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

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

…(3-1)

…(3-2)

…(3-3)

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

…(3-4)

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

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

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

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

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

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

参考書