ユークリッドの互除法
(問題) 1071 と 1029 の最大公約数を求める。
1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。
上の例で出てきた、1071 と 1029 の最大公約数を求める過程は、次のように表せる。
1071 = 1029 × 1 + 42 , 1029 = 42 × 24 + 21 , 42 = 21 × 2. {\displaystyle {\begin{aligned}1071&=1029\times 1+42,\\1029&=42\times 24+21,\\42&=21\times 2.\end{aligned}}}
すなわち、
1071 1029 = 1 + 42 1029 , 1029 42 = 24 + 21 42 , 42 21 = 2. {\displaystyle {\begin{aligned}{\frac {1071}{1029}}&=1+{\frac {42}{1029}},\\{\frac {1029}{42}}&=24+{\frac {21}{42}},\\{\frac {42}{21}}&=2.\end{aligned}}}
したがって、
1071 1029 = 1 + 1 24 + 1 2 {\displaystyle {\frac {1071}{1029}}=1+{\frac {1}{24+{\frac {1}{2}}}}}
このように、 n と m (n > m) の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数 n/m の連分数展開になっている。