Решение линейных диофантовых уравнений с любым числом неизвестных

Здравствуйте, уважаемые читатели! Продолжаю серию дилетантских статей о математике.

• Первая часть
• Вторая часть

Сегодня предлагаю поразмышлять над некоторой интересной математической задачкой.
А именно, давайте-ка для разминки решим следующее линейной уравнение:

«Чего сложного?» — спросите вы. Действительно, лишь одно уравнение и целых четыре неизвестных. Следовательно, три переменных есть свободные, а последняя зависит от оных. Так давайте выразим скорее! Например, через переменную , тогда множество решений следующее:

где — множество любых действительных чисел.

Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.

Вспомним про линейные уравнения с целыми коэффициентами и целыми корнями, которые, собственно, являются разновидностью диофантовых уравнений. Конкретно — наложим на наше уравнение соответствующие ограничение на целочисленность коэффициентов и корней. Коэффициенты при неизвестных у нас и так целые (), а вот сами неизвестные необходимо ограничить следующим:

где — множество целых чисел.

Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить как рациональное (дробное) число. Так как же решить это уравнение исключительно в целых числах?

Заинтересовавшихся решением данной задачи прошу под кат.

А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:

Задача выглядит по-прежнему непонятной, в таких случаях математики обычно производят какую-нибудь замену. Давайте и мы с вами её бахнем:

Опа, мы с вами достигли интересного результата! Коэффициент при у нас сейчас равен единице, а это значит, что мы с вами можем выразить эту неизвестную через остальные неизвестные в этом уравнении без всяких делений (чем грешили в самом начале статьи). Сделаем это:

Обращу внимание, что это говорит нам о том, что какие бы не были (в рамках диофантовых уравнений), всё равно останется целым числом, и это прекрасно.

Вспоминая, что справедливо говорить, что . А подставив заместо полученный выше результат получим:

Тут мы также видим, что что какие бы не были , всё равно останется целым числом, и это по-прежнему прекрасно.

Тогда в голову приходит гениальная идея: так давайте же объявим как свободные переменные, а будем выражать через них! На самом деле, мы уже это сделали. Осталось только записать ответ в систему решений:

Теперь можно лицезреть, что в системе решений нигде нет деления, а это значит, что всегда решения будут целочисленными. Попробуем найти частное решение исходного уравнения, положив, к примеру, что :

Подставим в исходное уравнение:

Тождественно, круто! Давайте попробуем ещё разок на другом примере?

Тут мы видим отрицательный коэффициент, он может доставить нам изрядных проблем, так что давайте от греха избавимся от него заменой , тогда уравнение будет следующим:

Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое — это брать коэффициенты из уравнения которые самые близкие к единице. Однако нужно понимать, что за скобку можно взять только лишь то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Итак:

Введем замену , тогда получим:

Вновь возьмем за скобку и наконец получим в уравнении неизвестную с единичным коэффициентом:

Введем замену , тогда:

Выразим отсюда нашу одинокую неизвестную :

Из этого следует, что какие бы мы не взяли, все равно останется целым числом. Тогда найдем из соотношения :

Аналогичным образом найдем из соотношения :

На этом наша система решений созрела — мы выразили абсолютно все неизвестные, не прибегая к делению, тем самым показывая, что решение точно будет целочисленным. Также не забываем, что , и нам надо ввести обратную замену. Тогда окончательная система решений следующая:

Таким образом, осталось ответить на вопрос — а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:

Для его решения в целых числах достаточно выполнение следующего условия:

(где — наибольший общий делитель).

Доказательство

Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.

Резюмируя вышесказанное, выпишем алгоритм действий для решения линейных диофантовых уравнений с любым числом неизвестных:

1. Проверяем, а решаемо ли уравнение вообще (вышеописанным свойством ). Если ответ положительный — переходим к следующему пункту.
2. Для ускорения процесса поделим все коэффициенты (включая свободный член) на их .
3. Избавляемся от отрицательных коэффициентов в уравнении заменой
4. Проводим серию замен (разваливая некоторые члены уравнения на суммы и объединяя их в скобки) таким образом, чтобы в конце концов один из членов уравнения был с единичным коэффициентов, и мы смогли вывести его без какого либо деления. Помня при этом, что за скобку можно взять только то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Наконец, объявляем все переменные, через которые выражена оная, как свободные.
5. Выводим остальные переменные через вышевыведенную (выводим из всех наших замен), не забывая также про обратные замены.
6. Объединяем все в единую систему решений.

В заключение стоит сказать, что также можно добавить ограничения на каждый член уравнения в виде неравенства на оного (тогда к системе решений добавляется система неравенств, в соответствии с которой нужно будет скорректировать ответ), а также добавить ещё чего-нибудь интересное. Ещё не стоит забывать и про то, что алгоритм решения является строгим и поддается записи в виде программы для ЭВМ.

С вами был Петр,
спасибо за внимание.