Beyond the State-of-the-Art

最先端を超えたいと思ってる(大嘘)エンジニアのブログ

aとbの最大公約数はbとa-bの最大公約数に等しい

このツイートの「aとbの最大公約数はbとa-bの最大公約数に等しい」」という事実が気になったので、実際に示しました。

abの最大公約数をc_1とすると、a = a_1 c_1, \; b = b_1 c_1 と表せます。ここでa_1b_1は互いに素な整数です。 これを使うと、a - b = c_1 (a_1 - b_1) と計算できます。

ここで背理法を使います。ba-bの最大公約数がc_1でないと仮定すると、b_1a_1 - b_1は1より大きい公約数を持ちます。 それをc_2と書くと、 a_1 - b_1 = c_2 a_2, \; b_1 = c_2 b_2と書けます。 この2式を整理すると、 a_1 = c_2 (a_2 + b_2), b_1 = c_2 b_2となります。 a_1b_1は1より大きい公約数c_2を持つことになり、互いに素であることに矛盾します。■