ユークリッドの互除法
まずはユークリッドの互除法について確認。
ユークリッドの互除法は2つの正整数の最大公約数をもとめる手法。
2つの正整数をm, nとする
- E1. mをnで割った剰余をrとする
- E2. rが0に等しければ終了。nが最大公約数である。
- E3. m <- n、n <- rとしてE1に戻る。
ここで<-は代入操作を表す記号とする。
拡張されたユークリッドの互除法
2個の正整数m, nについて、その最大公約数がdであるとする。
このとき、2個の整数a, bを用いて
am + bn = d
という式を成立させることができる。
拡張ユークリッドの互除法は最大公約数dだけでなく、上式における係数a, bを同時に求める。
- E'1. a <- 0, a' <- 1, c <- m, b <- 1, b' <- 0, d <- n
- a, a', b, b'の値はam+bn=d, a'm+b'n=cが成立するように選ばれている
- E'2. cをdで割った商をq, 余りをrとする
- E'3. r = 0なら終了。dは最大公約数であり、式am+bn=dは成立したままなのでa, bの値を参照すればよい。
- E'4-1. c <- d, d <-r
- ユークリッドの互除法におけるE3の手順と同様。
- cとdが変更されたので、等式am+bn=d, a'm+b'n=cが成立するように各係数を変更する必要がある。
- cにdを代入したので、a'm+b'n=cを成立させるにはa'にaを、b'にbを代入すればよい
- dにrを代入したので、am+bn=dを成立させるにはaにa'-qaを、bにb'-qbを代入すればよい(※)
- 上述の代入を一度に行うには、一時変数tを用意して
- E'4-2. t <- a', a' <- a, a <- t - qa, t <- b', b' <- b, b <- t - qb
- 代入後、E2へ戻る。
※部分の解説
(各変数はE'4-1の代入を行う前の値とする)
- r = c - qdと表せるので、d = (c-r)/q
- am + bn = dに代入して、am + bn = (c-r)/q
- 整理して -qam - qbn + c = r
- a'm + b'n = cを代入して整理すると(a'-qa)m + (b'-qb)n = r
