ユークリッドの互除法
a, b は自然数で a ≠ 0 とする。 b を a で割った商を q、剰余を r とすると
b = qa + r
今、d0 を a と r の両方を割り切る自然数とする。
このとき d0 は積 qa を割り切るから、和 qa + r も割り切るが、qa + r は b に等しい。したがって、d0 は a とb を割り切る。すなわち a と r の公約数はすべてb と aの公約数である。
逆に、d1 を b と a の両方を割り切る自然数とする。
d1 は qa を割り切るから差 b - qa を割り切るが、b - qa は r に等しい。したがって、d1 は a とrを割り切る。言い換えると b と a の公約数はすべてa と r の公約数である。
したがって、b と a の公約数全体の集合は a と r の公約数全体の集合に等しく、特に b と a の最大公約数は a と r の最大公約数でなければならない。