ユークリッドの互除法 とは

自然数（または整式）の最大公約数を求める方法の一つ。2つの自然数a,b ( a ≧ b )について、aをbで割った余りをrとすると、aとbの最大公約数は、bとrの最大公約数に等しい。このことを利用して割り算を繰り返し、2つの自然数の最大公約数を求める方法をユークリッドの互除法といいます。操作を繰り返して最後に割り切れた時の「割る数」が求める最大公約数となります。
1. aを bで割り，余り rを求める
2. bをrで割り、余りr1を求める
3. rをr1で割り、余りr2を求める
…これを繰り返す…
4. 余りが0になったときの割る数がaとbの最大公約数となる