Алгоритм Евклида

Разделить целое число a на число b с остатком – это значит найти такие числа q и r c 0 £ r < |b|, при которых выполняется равенство

a = q · b + r.

Разделить многочлен f на многочлен g с остатком – это значит найти такие многочлены q и r c 0 £ deg r < deg g, при которых выполняется равенство

f = q · g + r.

Для вычисления НОД(r₀ = a, r₁ = b) производится деление с остатком по следующей схеме:

a = r₀ = q₁r₁ + r₂,

b = r₁ = q₂r₂ + r₃,

.....

r_m-2 = q_m-1b_m-1 + r_m,

r_m-1 = q_mr_m.

Работа алгоритма Евклида основана на том, что отображение сохраняет наибольший общий делитель.

Отображение работает до a = НОД, b = 0.