o) まずは (単位行列)にとる。必然的にこのとき
,
である。
(計算):次の i),ii) を繰り返す
i) =0 なら (仕上げ) に進む。
ii) を
で割った商を
, 余りを
とおくと、
なる関係に着目する。右辺にでてくる二次行列の逆行列は 直ちに計算できて、
(仕上げ)さて、 になったはずである。 このとき、
![]() |
(I) |
他方、
に注意すると、
(II) は
の倍数である。
(I),(II) をあわせると、 は
の最大公約数
と
等しくなければならないことが分かる。
すなわち、(仕上げ)まですすんだところで の成分の
と、
が求めるものになる。