ユークリッドの互除法で悩んでいます．
これの証明は，たとえば wikipedia
https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95
にもあるとおりなんですが，このアルゴリズムで公約数のうちの「最大」が得られる理由がわかりません．
なぜ最大のものが互除法であぶり出されるのでしょうか？