ユークリッドの互除法

法でみた倍数 で考察したように，
次のことは同値である。

整数 a, b について，

• a と b は互いに素である。
• 積 ab は a と b の最小公倍数である。
• b を法としたとき aの倍数で 1 と合同なものがある。
• ax + by = 1 を満たす 整数 x, y がある。 (ディオファントス 1次 不定方程式)

整数 a, b について，
最大公約数を d とする。

• 積 ab は a と b の最小公倍数の d 倍である。
• b を法としたとき aの倍数で 合同な最小の自然数は d である。
• ax + by = c を満たす 整数 x, y があるための必要かつ十分な c の条件は， c が d の倍数であることである。

b を 法とするとき
a の倍数と a - bq (q は任意の整数) の倍数は一致する。
これを互除法の原理という。
(ひとつの説明)

a, b の最大公約数と
a - bq (q は任意の整数), b の最大公約数は等しい。