Помогите, пожалуйста, разобраться, на чем основан обобщенный алгоритм Евклида

Question

Читаю учебник по криптографии, наткнулся на небольшую мат/сводку по определениям и алгоритмам. Если "обычный" алгоритм Евклида по поиску наибольшего общего делителя мне понятен (даже не то, как им пользоваться-с этим любой разберется- а именно, на чем он основан) , т. е. первым действием мы проверим, не является ли меньше число само НОДом ( a mod b =0) , если нет, то стараемся найти НОД от меньшего числа и остатка от деления (таким оьразом выносится общий множитель) . Здесь все ясно (основной принцип - вынесение общего множителя за скобку) . То обощенный алгоритм я вобще не понял. Во-первых, причем здесь числа 1 и 0 в введенных автором строках U и V? Засчет чего мы в конечном итоге получаем числа x и y?

Answer 1

чего тут непонятного?
если с и r частное и остаток от деления a на b, то по определению деления с остатком:
a=b*c+r
Если у нас a и b делились на некоторое d, то есть a=a'd, b=b'd, то
a'd = b'dc+r, отсюда r= (a' - b') *d, а значит и r тоже делится на d.

То есть, a и b делились на какое-то число, то и r делится на это же число

Answer 2

Наверное, 0 и 1 нужны, чтобы было, с чего начать. Ведь мы ищем не одно число, а три. Фактически, этот алгоритм можно было расписать в два: сначала найти НОД от a и b, а затем найти его (НОДа) разложение по числам a и b. Зачем это толкать в единый алгоритм - непонятно.