2005年5月17日火曜日

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

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

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

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 の最大公約数 である.
というのが互除法の証明.

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

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

2 件のコメント:

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.