ユークリッドの互除法の原理
a,b,q,d,rを自然数とします
a÷b=q…r とします
このとき、
dがaとbの公約数である⇔dがbとrの公約数である
証明
まず(⇒)を示します
左側を仮定として右側を示すということです
dがaとbの公約数なので自然数m,nを用いて
a=md,b=nd と表せますので、これを代入すると
a÷b=q…r ⇔md÷nd=q…r
⇒md－ndq=r (わり算の定義より)
⇔d(m－nq)=r ・・・ (ア)
自然数から自然数の和または差または積は整数になるという法則(☆)があります
m－nqはこの法則が当てはまります
何故なら
①mは自然数
②nqは自然数(nとqが両方自然数だから)
①②より、m－nqも、自然数から自然数をひいた数です
したがってm－nqは整数なので
(ア)よりdはrの約数です
さらに仮定よりdはbの約数でもありましたから
"dがbとrの公約数である"と示せました。
次に(
)を示します
左側を仮定として右側を示すということです
さっきのmとnでなく新しくm,nを設定します
dがrとbの公約数なので自然数m,nを用いて
r=md,b=nd となるようなm,nが存在するので、これを代入すると
a÷b=q…r ⇔a÷nd=q…md
⇒a=ndq＋md (わり算の定義より)
⇔a=d(nq＋m) ・・・ (イ)
さっきの法則(☆)をまた使います
nqとmをは両方自然数なのでたしても自然数です
よって(イ)よりdはaの約数です
仮定よりdはbの約数でもあります
したがって"dがaとbの公約数である"と示せました
最大公約数の求め方への応用
ユークリッドの互除法の原理より、
aとbの最大公約数xはbとrの公約数でもあります(⇒より)ので
bとrの最大公約数をyとするとy≧x
一方yもaとbの公約数なのだが(
より)、aとbの最大公約数はxなのでx≧y
するとx=y
なので、aとbの最大公約数はbとrの最大公約数と一致します
なのでa÷bを計算してbとr(あまり)の最大公約数を求めれよいことになります
繰返し使うこともできます
bとrを新しくaとbと見なしておなじことをするのです
具体的な数字で実験してみてください
