最大公約数とユークリッド互除法 ― アルゴリズムの代数的基盤
gcd/lcmの定義と性質を厳密に定め，ユークリッド互除法の正当性と計算量$O(\log \min(a,b))$を証明する．ベズーの等式と拡張ユークリッド互除法を扱い，一次合同式$ax \equiv b \pmod{n}$の解法を体系的に解説する．
1 最大公約数と最小公倍数
定義 1 (最大公約数).
整数 （ともに でない）に対して， かつ を満たす正整数 の最大値を と の最大公約数（greatest common divisor）といい， と書く． のとき と は互いに素（coprime）であるという．
定義 2 (最小公倍数).
正整数 に対して， かつ を満たす正整数 の最小値を最小公倍数（least common multiple）といい， と書く．
定理 3.
正整数 に対して が成り立つ．
証明.
とおき，，（）と書く． を示せばよい． かつ は明らか． かつ なる正整数 に対して と書くと より ． なので ，よって ．したがって ． □
2 ユークリッド互除法
定理 4 (ユークリッド互除法の正当性).
正整数 に対して，割り算の原理より （）と書くとき， が成り立つ．
証明.
かつ ならば ．逆に かつ ならば ．よって と の公約数の集合は一致し，その最大値も一致する． □
注意 5.
この定理を繰り返し適用すれば と剰余が減少していき，最終的に に到達する．これがユークリッド互除法のアルゴリズムである．
定理 6 (計算量).
ユークリッド互除法の反復回数は である．
証明.
において であるが，実は が示せる． ならば ． ならば で ．よって2回の反復で剰余は半分以下になり，反復回数は ． □
3 ベズーの等式
定理 7 (ベズーの等式).
整数 （ともに でない）に対して， を満たす整数 が存在する．
証明.
集合 を考える．（ など）なので整列原理により最小元 が存在する． を示す．割り算の原理より （）とすると は の元． と の最小性より ，すなわち ．同様に ．よって は公約数．逆に かつ ならば なので ． □
4 拡張ユークリッド互除法
拡張ユークリッド互除法は，とともにベズーの係数（）を計算するアルゴリズムである．
例 8.
を計算する：，，，．よって ．逆代入すると ．
5 一次合同式の解法
定理 9.
合同式 が解を持つための必要十分条件は である．解が存在するとき， で 個の解を持つ．
証明.
は なる整数 の存在と同値である．ベズーの等式より なので， がこの集合に属する条件は である． のとき は より唯一解 を持ち，元の合同式の解は （）の 個である． □