$2$ つの整数の最大公約数を求める手法のひとつであるユークリッドの互除法(ごじょほう)について解説します．
ユークリッドの互除法とは，$2$ つの整数の最大公約数を求める方法のひとつです． 与えられた整数が大きい場合であっても，単純な手続きを繰り返すだけで最大公約数を求めることができます．
まず，$2$ つの正の整数の最大公約数を求める問題を考えてみましょう．
問 $8$ と $12$ の最大公約数を求めよ．
この問題を解く最も単純なやり方は，それぞれの正の約数をすべて書き出して，公約数となっている数の中で最大なものを求めればよいです． $8$ の正の約数は $1,2,4,8$ であり，$12$ の正の約数は $1,2,3,4,6,12$ です．これらの数の中で $8$ と $12$ の公約数となっているものは $2,4$ なので，最大公約数は $4$ とわかります．では，次の問題を考えてみましょう．
問 $14761$ と $4901$ の最大公約数を求めよ．
この問題も同じ方法で解くことが(原理的には)可能ですが，与えられた $2$ つの数がかなり大きいので，それぞれの数の約数をすべて求めるのは非常に大変です．そこで，それぞれの約数をすべて書き出すことなく，最大公約数を求めましょう．それを可能にするのがユークリッドの互除法です．まず，この具体例に対してユークリッドの互除法を適用したときの動きをみてましょう． はじめに，$14761$ を $4901$ で割ります． $$14761=4901\times 3 +58$$ $14761$ を $4901$ で割ると余りは $58$ となります． つぎに，$4901$ を $58$ で割ります． $$4901= 58\times 84 +29$$ 余りは $29$ となります． そして，$58$ を $29$ で割ります． $$58=29\times 2$$ 余りは $0$ です． すると，実は $29$ が $14761$ を $4901$ の最大公約数になっているのです．手続きを簡単に説明します．(より正確な説明は最後の節に書いてあります) まず，与えられた $2$ つの数の大きい方 (正確には小さくない方) を小さい方で割ります．余りが $0$ でなければ，小さい方の数をその余りで割ります．このように余りが $0$ となるまで割り算を繰り返していきます．すると，いずれ余りが $0$ になります．(後で証明します)このとき，実は割る数であった数がもとの $2$ つの数の最大公約数になっているのです．
結局，$2$ つの数の最大公約数を求めるためには上のように単に割り算を繰り返し実行するだけでよいのです．では，なぜこの方法で最大公約数が求められるのかを次節以降で説明していきます．
ユークリッドの互除法によって，$2$ つの数の最大公約数が正しく求められることを示すためには，次のユークリッドの互除法の原理とよばれる命題が重要になります． 簡単のために，整数 $x,y$ の最大公約数を $\gcd(x,y)$ と書くことにします．($\gcd$ は greatest common divisor の略)
たとえば，$\gcd(8,12)=4，\gcd(14761,4901)=29$ です．
ユークリッドの互除法の原理： 整数 $a,b,q,r$ が等式 $a=bq+r$ を満たすとき，$\gcd(a,b)=\gcd(b,r)$ が成り立つ．
証明： まず，$\gcd(a,b) \le \gcd(b,r)$ を示す． $r= a-qb$ であり，$\gcd(a,b)$ は $a,b$ の約数なので，→倍数関係と線形結合より，$r$ の約数でもある． したがって，$\gcd(a,b)$ は $b,r$ の公約数である．一方，$\gcd(b,r)$ は $b,r$ の最大公約数なので，$\gcd(a,b) \le \gcd(b,r)$ が成り立つ．
つぎに，$\gcd(b,r) \le \gcd(a,b)$ を示す． $a=bq+r$ であり，$\gcd(b,r)$ は $b,r$ の約数なので，→倍数関係と線形結合より，$a$ の約数でもある． したがって，$\gcd(b,r)$ は $a,b$ の公約数である．一方，$\gcd(a,b)$ は $a,b$ の最大公約数なので，$\gcd(b,r) \le \gcd(a,b)$ が成り立つ．
以上より，$\gcd(a,b) = \gcd(b,r)$ が示された．
ユークリッドの互除法の原理は，整数 $a,b,q,r$ が等式 $a=bq+r$ を満たすとき，$a$ と $b$ の最大公約数は $b$ と $r$ の最大公約数と等しいことを述べています．
ユークリッドの互除法の原理と除法の原理を用いて，ユークリッドの互除法の正当性を示します．ユークリッドの互除法の一般的な手続きはつぎのようになります．
ユークリッドの互除法の手続き： $2$ つの正の整数 $m,n$ の最大公約数を求める． step $1$: $m,n$ ($m\ge n \ge 0$) とする． step $2$: $n=0$ のとき，$m$ を出力して終了する．
step $3$: $m=nq+r~~(0\le r < n)$ を満たす整数 $q,r$ を求め，新しい $m$ を $n$ とし，新しい $n$ を $r$ とし，step $2$ へもどる．
ユークリッドの互除法の手続きでは，常に $2$ つの整数を保持します．はじめは $m,n$ を保持します． step $1$ で，$m\ge n$ となるようにします．つまり，小さくない方を $m$ とします．step $2$ で，$n=0$ ならば $m$ を出力して手続きを終了します．$n>0$ のときはstep $3$ へいきます．除法の原理により，$m=nq+r~~(0\le r < n)$ を満たす整数 $q,r$ が一意的に存在します．ここで，$0\le r < n$ という条件がついていることがポイントになります．そのような $q,r$ を割り算によって求めます． その後，保持する整数を $m,n$ から $n,r$ に変更します．つまり，さきほど保持していた $n$ と，割り算によって求まった余り $r$ を新たに保持します． さて，ユークリッドの互除法の手続きによって，$m,n$ の最大公約数が正しく求められることを示すためには，以下の二つのことを確かめる必要があります．
停止性: 手続きが有限回のステップで必ず停止すること．
正当性: 出力がはじめの $m,n$ の最大公約数になっていること．
それぞれについて，示していきます．
停止性の証明： 手続きはstep $2$ で $n=0$ のときに限り停止する．したがって，有限回のステップで $n=0$ となることを示せばよい． 手続きのはじめ，$n=0$ のときは明らかに停止する．$n>0$ とする．step $3$ で $r$ が新しい $n$ となるが，$0\le r < n$ なので，$n$ の値は真に減少する. $n$ は $0$ 以上の整数なので，有限回のステップで必ず $0$ となる．
正当性の証明： ユークリッドの互除法の原理より，$\gcd(m,n)=\gcd(n,r)$ である．したがって，保持している $2$ つの整数の最大公約数は常に変わらない．任意の整数 $x$ に対して $\gcd (x,0) =x$ なので，アルゴリズムが停止したときの $m$ (保持している $2$ つの数のうち小さくない方) の値が，はじめの $2$ つの数の最大公約数となる．
ユークリッドの互除法の原理によって，保持している $2$ つの整数の最大公約数は常に変わらないことが保証されます．さらに，除法の原理によって，保持している数のうち小さい方 (正確には大きくない方)の値は真に減少していきます．保持している数は常に $0$ 以上の整数なので，いずれ $0$ になるというわけです．このようにユークリッドの互除法は基本的な原理の組合せによって，その正当性が導かれます．
ユークリッドの互除法のように，有限回の基本的操作を繰り返して解を得る(あるいは解がないことを示す)ための手続きのことをアルゴリズムといいます．
