Расширенный алгоритм Евклида

Даны два целых числа a и b. Нам зачастую надо найти другие два целых числа, s и r, такие, которые

s × a + t × b = НОД(a,b)

Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t. Алгоритм и процесс такого вычисления показан на рисунке.

Здесь расширенный алгоритм Евклида использует те же самые шаги, что и простой алгоритм Евклида. Однако в каждом шаге мы применяем три группы вычислений вместо одной. Алгоритм использует три набора переменных: r, s и t.

На каждом шаге переменные r₁, r₂ и r используются так же, как в алгоритме Евклида.

Переменным r₁ и r₂ присваиваются начальные значения a и b соответственно.

Переменным s₁ и s₂ присваиваются начальные значения 1 и 0 соответственно.

Переменным t₁ и t₂ присваиваются начальные значения 0 и 1, соответственно.

Вычисления r, s и t одинаковы, но с одним отличием. Хотя r — остаток от деления r₁ на r₂, такого соответствия в других двух группах вычислений нет. Есть только одно частное, q, которое вычисляется как r₁/r₂ и используется для других двух вычислений.