自然数a, b に対して，a = bq + r なる
整数 q と 0 以上 b 未満の整数 r があります。
(
整数の乗法・除法)
b と r の公約数が d であるならば，d は a の約数です。
実際，
仮定より b = d b', r = d r' なる整数 b', r' があります。
a = bq + r = d b' q + d r' = d (b'q + r') なので， d は a の約数であることがいえました。
つまり，b と r の最大公約数と a と b の最大公約数は等しいことになります。