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

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

ユークリッドの互除法よりも、
｢aとbの最大公約数はbとa-bの最大公約数に等しい｣
の方を強調した方がいいと思うんですよ。

— ババ。 (@bbbbbankz1n) 2020年8月12日

との最大公約数をとすると、 と表せます。ここでとは互いに素な整数です。 これを使うと、 と計算できます。

ここで背理法を使います。との最大公約数がでないと仮定すると、とは1より大きい公約数を持ちます。 それをと書くと、と書けます。 この2式を整理すると、となります。 とは1より大きい公約数を持つことになり、互いに素であることに矛盾します。■