勉強時間の計測に時間時刻記録

2009年03月04日

最大公約数を求める(ユークリッドの互除法)

正整数a,b( a > b )の最大公約数を求める方法

aをbで割ったときの商をq、余りをrとすると
a = qb + r (0 ≦ r < b )
とあらわせます。
このときaとbの最大公約数を(a,b)であらわすと
(a,b) = (b,r)
が成り立ちます。(証明は下)
これを繰り返せばaとbの最大公約数を
それらより小さな2つの数を使って求められます。
例えばb,rに対して同じことをすれば
b = sr + t (0 ≦ t < r )
とあらわせるので
(b,r) = (r,t)
が成り立つ。
よって
(a,b) = (r,t)。


(1234,137)
1234 = 9*137 + 1
よって(1234,137) = (137,1) = 1

(376,24)
376 = 15*24 + 16
24 = 1*16 + 8
よって(376,24) = (16,8) = 8



a = qb + r (0 ≦ r < b )のとき(a,b) = (b,r)の証明
(以下aがbで割り切れることをa|bと書くことにします)

a,b,rはある整数s,t,u,vを用いて
a = (a,b)s …@
b = (a,b)t = (b,r)u …A
r = (b,r)v …B
とあらわせる。
よって
a
= qb + r
= q(b,r)u + (b,r)v (なぜならAB)
= (b,r)(qu + v)
すなわち (b,r)|a
さらに (b,r)|b だから
(b,r)はa,bの公約数である。
よって(b,r) ≦ (a,b) …C

r
= a - qb (なぜならa = qb + r)
= (a,b)s - q(a,b)t(なぜなら@A)
= (a,b)(s - qt)
すなわち (a,b)|r
さらに (a,b)|b だから
(a,b)はb,rの公約数である。
よって(a,b) ≦ (b,r) …D

CDより(a,b) = (b,r)
証明終了



別の証明

a,bの公約数をdとする。
このとき下の補題より
d|(a-qb)
よってdはb,rの公約数である。…E

逆に b,rの公約数をeとすると
a = qb + r
だから下の補題より e|a
よってeはa,bの公約数である。…F

EFよりa,bの公約数の集合とb,rのそれは一致する。
よってa,bの最大公約数とb,rのそれは同じである。
証明終了


別の証明の補題
d|a,d|b のとき次の二つが成り立つ。
d|ka (kは任意の整数)
d|(a+b)

なぜなら
d|a,d|bのときある整数s,tにより
a = sd
b = td
とあらわせる。
このとき
ka = k(sd) = (ks)d なので d|ka
a+b = sd + td = (s+t)d なので d|(a+b)
証明終了



以下の各テキストボックスに自然数を1つずつ入力してボタンを押すと最大公約数を求められます。









posted by qc at 16:48 | Comment(0) | その他 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
勉強時間の計測に時間時刻記録
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。