読者です 読者をやめる 読者になる 読者になる

ユークリッドの互除法

tex記法のテスト。
割られる数をA、割る数をBとする(A\div B)。
商をQ、余りをRとする(A\div B = Q...R)。
また、A>Bとしておく。
このとき、
A=QB+R  …(1)
であり、
0 \le R < B
である。また、ABに対し、QRはただ一つ定まる。
ABの共通の約数のうち最大のものを最大公約数と呼び、
D=\mathrm{gcd}(A, B)
であらわす。なお、\mathrm{gcd}(A, B) = 1となるような2数は「互いに素である」と言う。
Dとの関係でABを以下のように書きなおす。
A = Da
B = Db
同様に、d = \mathrm{gcd}(B, R)として、Bの別の表現
B = db'
を得、Rを以下のように書きなおす。
R = dr
今得た表現を式(1)に代入すると、
A = Qdb' + dr = d(Qb' + r)
となる。よって、dAの約数である。また、dBの約数でもあったので、結局dABの公約数でもあることがわかった。ABの最大公約数はDであったので、以下の関係を得る。
d\leq D  …(2)
ここで式(1)を変形し、
R = A - QB
さらにA = DaB = Dbを代入すると、
R = Dq - QDb = D(a - Qb)
となる。よって、DRの約数である。DBの約数でもあったので、DRBの公約数である。RBの最大公約数はdであったので、以下の関係を得る。
D\leq d  …(3)
ここで(2)と(3)を比べると、結局
D = d
であることがわかる。すなわち、
\mathrm{gcd}(A, B) = \mathrm{gcd}(B, R)
であり、文章で表現すると、「2数ABの最大公約数は、ABで割った余りRBの最大公約数に等しい」ということである。
またここで今のBRを新たなABとして同様の手順を繰り返すこともできる。
abをスタートにして繰り返してみよう。
a = bq_1 + r_1 (r_1 < b
b = r_1q_2 + r_2 (r_2 < r_1
r_1 = r_2q_3 + r_3 (r_3 < r_2
(中略)
r_{n-1} = r_nq_{n+1} + r_{n+1} (r_{n+1} = 0 < r_n
この時、余りrは正の整数であり、一つ前のステップの余りより必ず小さくなるため、有限回の繰り返しで0になり、繰り返しが終了するというのが重要である。
\mathrm{gcd}(x, 0) = xであるので(全ての数は0の約数である)、r_n = Dである。
実際の手順としては、
a\div b = q_1...r_1
b\div r_1 = q_2...r_2
r_1\div r_2 = q_3...r_3
(中略)
r_{n_1}\div r_n = q_{n+1}...0
と、余りが0になるまで割り算を繰り返す(剰余を求る)ことで最大公約数を求めることができる。
これをユークリッドの互除法と呼ぶ。