Есть более простой способ на сайте кафедры теории чисел мехмата МГУ.
Кратко: для уравнения a_1*x_1+… + a_n * x_n = b строим матрицу из n+1 строк и n столбцов. Первая строка — коэффициенты при неизвестных в уравнении, оставшаяся часть — единичная матрица. Приводим матрицу к такому виду, что вся элементы первой строки нулевые за исключением первого, который равен НОД. преобразованиями столбцов: умножение столбца на -1, прибавление к стобцу любого другого, умноженного на целое число, умножение столбца на -1. Тогда элементы первой строки будут результатом подстановки соответствующих столбцов в выражение. А ответ — первый столбец, домноженный на b/НОД плюс остальные столбцы, домноженные на любые целые числа.
Кратко: для уравнения a_1*x_1+… + a_n * x_n = b строим матрицу из n+1 строк и n столбцов. Первая строка — коэффициенты при неизвестных в уравнении, оставшаяся часть — единичная матрица. Приводим матрицу к такому виду, что вся элементы первой строки нулевые за исключением первого, который равен НОД. преобразованиями столбцов: умножение столбца на -1, прибавление к стобцу любого другого, умноженного на целое число, умножение столбца на -1. Тогда элементы первой строки будут результатом подстановки соответствующих столбцов в выражение. А ответ — первый столбец, домноженный на b/НОД плюс остальные столбцы, домноженные на любые целые числа.