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

Разделить целое число 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 -1} b_{m -1} + r_m,

r_{m -1} = q_mr_m.

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

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