ユークリッド互除法

目的

最近ユークリッド互除法をコードに落とし込む機会があったのですが, 自分の理解を整理できていなかったのでまとめます.

ユークリッド互除法とは

2 つの自然数 a, b の最大公約数を計算する方法です.

自然数 a, b の最大公約数を gcd(a, b) と表す場合, 以下の定理を用いて計算します.

a > b \in \mathbb{N} とし, a を b で割ったときの商を q \in \mathbb{N} 余りを r とする.

つまり a = b \times q + r, 0 \leq r < b
このときに gcd(a, b) = gcd(b, r) となる

例1. gcd(130, 156)

まず, a = 156, b = 130 として, a = b \times q + r の式を埋めてみましょう.
156 = 130 \times 1 + 26

ユークリッドの互除法より, gcd(a, b) = gcd(b, r) です.
なので, a' = b, b' = r として a' = b' \times q' + r' を埋めると以下の様になります.
130 = 26 \times 5 + 0

このとき, b' = 26 と r' = 0 の最大公約数は 26 であることが明らかです.
よって, 26 が最大公約数となります.

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

それでは, gcd(a, b) = gcd(b, r) となることを証明します.
ここで G = gcd(a,b), G' = gcd(b, r) \in \mathbb{N} と定義します.

まずこの式に立ち返りましょう. a = b \times q + r

  1. a = b \times q + r, G' = gcd(b, r) より, a = G'( b \times q' + r') が成り立ちます.
    よって, a, b は共に G' を因数に含むことがわかります.
    そして, G = gcd(a,b) なので, G' \leq G であることがわかります.

  2. a = b \times q + r より, r = b \times q - a であることに注目すると,
    r = b \times q - a, G = gcd(a, b) より, r = G( b \times q' + a') が成り立ちます.
    よって, r, b は共に G を因数に含みます.
    そして, G' = gcd(b,r) なので, G \leq G' であることがわかります.

1, 2 より gcd(a, b) = gcd(b, r) が成り立ちます.

参考文献