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

Алгоритм Евклида быстро находит наибольший общий делитель через повторение операции остатка. Расширенный вариант вычисляет коэффициенты Безу и применяется в теории сравнений.