最大公約数を求めるとき、どうしますか？ ぼくが中学校で教わったのは2つの数を素因数分解する方法です。分かりやすいんですが、素因数分解はラクではないのです。相手にする数がちょっと大きくなるともういきなり計算できなくなってしまいます。実際、1031を素因数分解してみてください。電卓を使っても大変だと思います……。最大公約数は色々な場面で出てきますし、効率的な方法があれば素晴らしい！
互除法というのがあるのです。まず記号を約束しましょう。(ａ，b)でａ，ｂの最大公約数を表すことにします。例えば、(12，8)＝４、というように使います。これを(8，12)と書いてもＯＫです（値は入れ替えてもよい）。つまり(12，8)＝(8，12)＝4です。このとき実は(ａ，ｂ)＝(ａ－ｂ，ｂ)が成立するのです。例えば、(700，120)＝(580，120)です。さらに(580，120)＝(460，120)＝(340，120)＝(220，120)＝(100，120)と続けることもできます。ここで、(100，120)＝（120，100）ですから(100，120)＝（120，100）＝(20，100)。結局(700，120)＝(20，100)、つまり最大公約数は20です。面倒くさそうですが引き算しか使っておらず、素因数分解はせずに最大公約数を求めることができるのです。実際には何度も引き算するのはバカバカしいですから、(700，120)＝(100，120)と一気に変形します（これが互除法）。700÷120＝5、余り100、とすればよいのです。教科書に不定方程式というのが出てきます。これを解くのにも互除法を使えます。
(ａ，ｂ)＝(ａ－ｂ，ｂ)を証明しましょう。ａ，ｂの公約数をｄとします。このときａ＝ｍｄ、ｂ＝ｎｄですから（ｍ、ｎは整数）、ａ－ｂ＝ｍｄ－ｎｄ＝(ｍ－ｎ)ｄ。よってａ－ｂはｄで割り切れます。従ってｄはａ－ｂ、ｂの公約数でもあるわけです。今度はａ－ｂ、ｂの公約数をｄとしましょう。ａ－ｂ＝ｍｄ、ｂ＝ｎｄですからａ＝ｍｄ＋ｂ＝ｍｄ＋ｎｄ＝(ｍ＋ｎ)ｄ。よってａはｄで割り切れますから、ｄはａ，ｂの公約数です。結局、ａ，ｂの公約数はａ－ｂ，ｂの公約数に一致します。最大公約数は公約数の中の最大のものなのだから、最大公約数も一致します。なお、割り算は引き算の繰り返しで実現できますから「互除法」もこれで証明されたことになります。
互除法の使用例を挙げておきましょう。
(390，273)＝(117，273) （390÷273＝１ 余り117）
(117，273)＝(273，117)＝(39，117) （273÷117＝2 余り39）
(39，117)＝(117，39)＝39 （117と39の最大公約数は39）
互除法はユークリッドの『原論』にあり「ユークリッドの互除法」とも呼ばれます。ぼくは見たことがありませんが、そこでは互除法でなく、今回示したような言わば「互減法」だそうです。割り算でなく、引き算をしているのだそうです。どちらにしても素因数分解とは計算量の点では比較になりません。極めて効率的な方法です。
