ユークリッドの互除法
ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。
ここで
K i = ( k i 1 1 0 ) {\displaystyle K_{i}={\begin{pmatrix}k_{i}&1\\1&0\\\end{pmatrix}}} とおくと、 | K i | = − 1 {\displaystyle |K_{i}|=-1} であるから K i − 1 {\displaystyle K_{i}^{-1}} は存在して
( k h − 1 1 1 0 ) − 1 ( k h − 2 1 1 0 ) − 1 . . . ( k 2 1 1 0 ) − 1 ( k 1 1 1 0 ) − 1 ( k 0 1 1 0 ) − 1 ( r 0 r 1 ) = ( r h 0 ) {\displaystyle {\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{h-2}&1\\1&0\\\end{pmatrix}}^{-1}...{\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}