У той час як "звичайний" алгоритм Евкліда просто знаходить найбільший спільний дільник двох чисел і, розширений алгоритм Евкліда знаходить крім НСД також коефіцієнти і такі, що:
Тобто він знаходить коефіцієнти, за допомогою яких НСД двох чисел виражається через самі ці числа.
Внести обчислення цих коефіцієнтів в алгоритм Евкліда нескладно, досить вивести формули, за якими вони змінюються при переході від пари до пари (знаком відсотка ми позначаємо взяття залишку від ділення).
Отже, нехай ми знайшли рішення задачі для нової пари:
і хочемо отримати рішення для нашої пари:
Для цього перетворимо величину:
Підставами це в наведене вище вираз з і і отримаємо:
і, виконуючи перегрупування доданків, отримуємо:
Порівнюючи це з вихідним виразом над невідомими і, отримуємо необхідні вирази:
Реалізація
База рекурсії - випадок. Тоді НОД дорівнює, і, очевидно, необхідні коефіцієнти і рівні і відповідно. В інших випадках працює звичайне рішення, а коефіцієнти перераховуються за вищеописаним формулами.
Розширений алгоритм Евкліда в такий реалізації працює коректно навіть для негативних чисел.