ユークリッドの互除法 |
m を n で割ったときのあまりを r1 とする。 |
n を r1 で割ったときのあまりを r2 とする。 |
r1 を r2 で割ったときのあまりを r3 とする。 |
……………………………… |
以上の処理を続けていくと,いつか次のようになる。 |
rk-1 を rk で割ると割り切れる。 |
このとき,m と n の最大公約数は,rk になる。 |
ユークリッドの互除法(補題1の追加版) | |
m を n で割ったときのあまりを r1 とすると, | FmとFnの最大公約数 = FnとFr1の最大公約数 |
n を r1 で割ったときのあまりを r2 とすると, | FnとFr1の最大公約数 = Fr1とFr2の最大公約数 |
r1 を r2 で割ったときのあまりを r3 とすると, | Fr1とFr2の最大公約数 = Fr2とFr3の最大公約数 |
……………………………… | ……………………………… |
以上の処理を続けていくと,いつか次のようになる。 | |
rk-1 を rk で割ると割り切れる。このとき, | 性質7により,Frk-1 は Frk で割り切れる。よって,Frk-1 と Frk の最大公約数は Frk になる。 |
よって,m と n の最大公約数は,rk になる。 | したがって,FmとFnの最大公約数 = Frk |
以上のことから,FmとFnの最大公約数 = Frk = Fmとnの最大公約数 となり,性質9が証明されました。
(証明終わり)