このツイートの「aとbの最大公約数はbとa-bの最大公約数に等しい」」という事実が気になったので、実際に示しました。
ユークリッドの互除法よりも、
— ババ。 (@bbbbbankz1n) 2020年8月12日
「aとbの最大公約数はbとa-bの最大公約数に等しい」
の方を強調した方がいいと思うんですよ。
と
の最大公約数を
とすると、
と表せます。ここで
と
は互いに素な整数です。
これを使うと、
と計算できます。
ここで背理法を使います。と
の最大公約数が
でないと仮定すると、
と
は1より大きい公約数を持ちます。
それを
と書くと、
と書けます。
この2式を整理すると、
となります。
と
は1より大きい公約数
を持つことになり、互いに素であることに矛盾します。■