ユークリッドの互除法

二つの整数aとb（a > b）の最大公約数（GCD）は、bとaをbで割った余りrの最大公約数に等しい。数式で表すと、\(\gcd(a, b) = \gcd(b, r)\)。ここで、\(r = a \mod b\)である。

ユークリッドの互除法は、二つの整数の最大公約数を効率的に求めるアルゴリズムである。この方法は整数論の基礎であり、現代の暗号理論などにも応用される重要な手法である。

二つの整数aとb（a > b）を考え、aをbで割った商をq、余りをrとする。\(a = bq + r\)が成り立つ。

\(d = \gcd(a, b)\)とし、dがbとrの公約数でもあることを示す。

dはaとbの公約数であるため、\(a = d \cdot m\)、\(b = d \cdot n\)と表せる。

\(r = a - bq = d \cdot m - d \cdot n \cdot q = d(m - nq)\)となるため、dはrの約数でもある。

次に、dがbとrの最大公約数であることを示す。\(\gcd(b, r) = d'\)とし、d'がaとbの公約数でもあることを示す。

d'はbとrの公約数であるため、\(b = d' \cdot n'\)、\(r = d' \cdot m'\)と表せる。

\(a = bq + r = d' \cdot n' \cdot q + d' \cdot m' = d'(n'q + m')\)となるため、d'はaの約数でもある。

したがって、d'はaとbの公約数であり、d' ≤ dが成り立つ。

dはbとrの公約数であり、d'はaとbの公約数であるため、d = d'が成り立つ。

以上より、\(\gcd(a, b) = \gcd(b, r)\)が証明される。(証明終)