Пусть — натуральные числа, удовлетворяющие условиям
Шаг 1. С помощью обобщённого алгоритма Евклида найти . Найти такое, что .
Шаг 2. Для очередного значения найти числа по следующим правилам:
при :
— частное от деления на , за исключением случая, когда нечётно и остаток от деления равен нулю.
Шаг 3. Для очередного выбора найти все целые числа , удовлетворяющие условиям
,
если четное,
если нечетное.
Шаг 4. Для каждого c из шага 3 решить в целых числах систему уравнений
Если и окажутся неотрицательными целыми числами, то добавить
Шаг 5. Если , то алгоритм заканчивает работу. Иначе, возвращаемся на шаг 2 к следующему значению .