問題を解決する定型的な手法・技法

のことをいう（広辞苑）．
　別の言い方をすれば，「戦略的で大がかりな計算法」のことを算法というのである．

　互除法の実例をあげよう．

例題1　A＝1000，B＝310 の最大公約数を求めよ．
　解

　最大公約数は 10 である．

類題　次の自然数の最大公約数を求めよ．
　（1）84，　48
　（2）880，4200

　互除法は，通常はこのように「最大公約数を求める方法」として知られているが，われわれは互除法を「ある数列を作り出す方法」と考えよう．

α，βは与えられた自然数とする．そこで，α₀＝α，α₁＝βとおき，
　　　α₀ をα₁ で割ったときの商をθ₁，余りをα₂
　　　α₁ をα₂ で割ったときの商をθ₂，余りをα₃
　　　α₂ をα₃ で割ったときの商をθ₃，余りをα₄
　　　……
とする．
　このとき，

　　　α₁ ＞ α₂ ＞ α₃ ＞ α₄ ＞　……

　となるので，ある時点でα_k＝ 0 となる．
　そこで，α_ν＞ 0 ，α_ν＋1＝ 0 とする．

　このとき，次の関係式が成り立つ．

　　　α₀＝α₁θ₁＋α₂，　　　　0＜α₂＜α₁
　　　α₁＝α₂θ₂＋α₃，　　　　0＜α₃＜α₂
　　　α₂＝α₃θ₃＋α₄，　　　　0＜α₄＜α₃
　　　……
　　　α_ν−2＝α_ν−1θ_ν−1＋α_ν，　0＜α_ν＜α_ν−1
　　　α_ν−1＝α_νθ_ν

この状況を次の図式で表すことにする．

この図で，最初の部分

は，

　　　α₀ をα₁ で割ったときの商がθ₁で余りが α₂である

ことを示している．
　他の部分も同様である．

　さて，一般に，

　　　　A＝BQ＋R　

という関係式があると，

　　　　A， B の公約数は R の約数であり，B，R の公約数は A の約数である．

したがって，

　　　（A，Bの公約数）＝（B，Rの公約数）

となる．
　よって，双方の公約数のうち一番大きいものは等しくなければならない．つまり，

　　　（A，Bの最大公約数）＝（B，Rの最大公約数）

となる．
　整数 α，β の最大公約数を（α，β）と書くと，

　　　A＝BQ＋R　のとき，　（A，B）＝（B，R）　

このことを，上の関係式にあてはめると，

　　　α₀＝α₁θ₁＋α₂　　　　　　　　→　　（α₀，α₁）＝（α₁，α₂）
　　　α₁＝α₂θ₂＋α₃　　　　　　　　→　　（α₁，α₂）＝（α₂，α₃）
　　　α₂＝α₃θ₃＋α₄　　　　　　　　→　　（α₂，α₃）＝（α₃，α₄）
　　　……
　　　α_ν−2＝α_ν−1θ_ν−1＋α_ν　　　→　　（α_ν−2，α_ν−1）＝（α_ν−1，α_ν）
　　　α_ν−1＝α_νθ_ν

　また，最後の関係から，　　（α_ν−1，α_ν）＝α_ν
よって，

　　　（α₀，α₁）＝（α₁，α₂）＝（α₂，α₃）＝……＝（α_ν−1，α_ν）＝α_ν

つまり，最後の自然数が最初の2数 α₀＝α，α₁＝β の最大公約数であることが示された．

例題2　A＝108，B＝472 の最大公約数を求めよ．
　解

　最大公約数は 4

　ここできまる数列

　　　　　α₀，α₁，α₂，α₃，……，α_ν−1，α_ν，0

を（自然数の組 α，βに対し）互除法できまる数列と呼ぼう．