割り算からわかること
割り算の一般式は次の方法で表記できることがわかっている。
…(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が存在することもわかる。
コメント ※節度あるコメントをご協力をお願いたします。