Comments 11
Для его решения в целых числах необходимо выполнение следующего условия:
N mod GCD(a1,a2,..,an)=0
…
Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи.
Можно же буквально одной фразой написать: все a_i делятся на GCD, поэтому вся левая часть уравнения делится на него — значит и правая должна делиться, чтобы было решение.
Это необходимое условие для доказательства, но не достаточное.
Иными словами, из этого нет прямого следствия, что в таком случае решение будет (бесконечное множество решений).
Ну и \cdot всё же. Вместо *. Спасибо.
Без искомого «нарочито-весёлого стиля повествования» статья не будет отличаться от сухого изложения из мат. учебников, я же пытаюсь хоть как-то внести жизнь и атмосферу в текст и вообще пообщаться с читателями, для меня это очень важно.
По поводу \cdot вы совершенно правы, спасибо.
Кратко: для уравнения a_1*x_1+… + a_n * x_n = b строим матрицу из n+1 строк и n столбцов. Первая строка — коэффициенты при неизвестных в уравнении, оставшаяся часть — единичная матрица. Приводим матрицу к такому виду, что вся элементы первой строки нулевые за исключением первого, который равен НОД. преобразованиями столбцов: умножение столбца на -1, прибавление к стобцу любого другого, умноженного на целое число, умножение столбца на -1. Тогда элементы первой строки будут результатом подстановки соответствующих столбцов в выражение. А ответ — первый столбец, домноженный на b/НОД плюс остальные столбцы, домноженные на любые целые числа.
Возможно слишком поздно, но напишу, все-таки.
Задача решения такого уравнения на N целых переменных решается с итеративным применением расширенного алгоритма Эвклида. Этот алгоритм для двух чисел a и b находит их GCD() а вместе с ним коэффициенты x и y. т.ч x*a+y*b=gcd(a,b). Фактически, решает задачу для двух переменных.
Далее можно добавить следующую переменную просто решив уравнение x*gcd(a1,...,ak) + y*a(k+1) = gcd(a1,...,a(k+1)), опять применив этот же алгоритм. Если подставить предыдущее решение вместо gcd(a1,..., ak) и раскрыть скобки, то мы получим решение задачи для k+1 переменной. Иными словами, надо решить новую задачу для двух переменных и домножить на x все предыдущие переменные и взять y для последней переменной. В итоге мы всегда получим линейную комбинацию всех коэффициентов, дающую их GCD. Остается в конце домножить все на b/gcd(a1,...,an) чтобы получить решение для b. Это заодно является конструктивным доказательством, что любое число, делящееся на GCD всех коэффициентов всегда можно получить.
Сложность этого алгоритма O(n log M), где n — количество переменных, а M — максимальный коэффициент.
Описанный в статье алгоритм, в общем-то, и есть неявное применение алгоритма эвклида (все эти вычитания одного коэффициента из другого). Но мое описание, мне кажется, гораздо понятнее и проще.
Решение линейных диофантовых уравнений с любым числом неизвестных