ユークリッドの互除法の証明

今年は数学を教えていないので，忘れないために，たまには数学メモ．
ユークリッドの互除法 ＞　（約分に使った記事）

これの原理の証明をメモ．

AをBで割った商がq，余りRのとき，A=Bq+R　…(1)
AとBの最大公約数をGとすると，A=Ga，B=Gb（a,bは互いに素）
(1)式に代入して，Ga=Gbq＋R，
移項して，Gでくくると，G(a-bq)＝R
ここからGはRの約数であることがわかる．
そこで，R=Grとおく．

代入して，Gで割ると，a=bq＋r,ここでbとrに公約数gが存在し，b=gc,r=gsとおく.
すると，a=g(cq+s)となり，gはaの約数になる．
これは，aとbが互いに素であることに反する．
従って，GはB，Rの最大公約数である．

仮定と，結論をつなげると
A=Bq+Rのとき，A，Bの最大公約数はB，Rの最大公約数である．

この事実を繰り返し用いるのが，ユークリッドの互除法である．


たとえば，348 と 252 の最大公約数は
348 = 252 × 1 + 96 より 348÷252 の余り 96 に含まれる．

続いて，252 と 96 の最大公約数は
252 = 96 × 2 + 60 より 252÷96 の余り 60 に含まれる．

さらに続いて，96 と 60 の最大公約数は
96 = 60 × 1 + 36 より 96÷60 の余り 36 に含まれる．

さらに続いて，60 と 36 の最大公約数は
60 = 36 × 1 + 24 より 60÷24 の余り 12 に含まれる．

最後に 24 と 12 の最大公約数は 12


これを遡れば，
12 と 24 の最大公約数は
24 と 36 の最大公約数 であり
36 と 60 の最大公約数 であり
60 と 96 の最大公約数 であり
96 と 252 の最大公約数 であり
252 と 348 の最大公約数 である．
というのが互除法の証明．

＞追記：「ユークリッドの互除法の証明の意味」

＞くろべえ「互除法」関連の記事