はじめに 競プロをやってると、2つの自然数の最大公約数を求める問題が出てくる。 その時に使うのがユークリッドの互除法という手法。 ユークリッドの互除法がなぜ成り立つのか考えたのをまとめる。 （厳密な証明ではなく、ユークリッドの互除法がなぜ成立す…