ユークリッド互除法 ユークリッドの互除法と言うのはご存知でしょうか。 2つの数の最大公約数を求めるアルゴリズムですね。例えば、390と91ではこうなります。 \[\begin{aligned} 390 &= 91 \times 4 + 26 \\ 91 &= 26 \times 3 + 13 \\ 26 &= 13 \times 2 +…