![image](https://habrastorage.org/web/b3e/ed4/8b8/b3eed48b8bde4018835369e1c2dbe4ce.png)
Здравствуйте, уважаемые читатели! Продолжаю серию дилетантских статей о математике.
Сегодня предлагаю поразмышлять над некоторой интересной математической задачкой.
А именно, давайте-ка для разминки решим следующее линейной уравнение:
«Чего сложного?» — спросите вы. Действительно, лишь одно уравнение и целых четыре неизвестных. Следовательно, три переменных есть свободные, а последняя зависит от оных. Так давайте выразим скорее! Например, через переменную
где
Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.
Вспомним про линейные уравнения с целыми коэффициентами и целыми корнями, которые, собственно, являются разновидностью диофантовых уравнений. Конкретно — наложим на наше уравнение соответствующие ограничение на целочисленность коэффициентов и корней. Коэффициенты при неизвестных у нас и так целые (
где
Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить
Заинтересовавшихся решением данной задачи прошу под кат.
А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:
Задача выглядит по-прежнему непонятной, в таких случаях математики обычно производят какую-нибудь замену. Давайте и мы с вами её бахнем:
Опа, мы с вами достигли интересного результата! Коэффициент при
Обращу внимание, что это говорит нам о том, что какие бы не были
Вспоминая, что
Тут мы также видим, что что какие бы не были
Тогда в голову приходит гениальная идея: так давайте же
Теперь можно лицезреть, что в системе решений нигде нет деления, а это значит, что всегда решения будут целочисленными. Попробуем найти частное решение исходного уравнения, положив, к примеру, что
Подставим в исходное уравнение:
Тождественно, круто! Давайте попробуем ещё разок на другом примере?
Тут мы видим отрицательный коэффициент, он может доставить нам изрядных проблем, так что давайте от греха избавимся от него заменой
Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое — это брать коэффициенты из уравнения которые самые близкие к единице. Однако нужно понимать, что за скобку можно взять только лишь то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Итак:
Введем замену
Вновь возьмем за скобку и наконец получим в уравнении неизвестную с единичным коэффициентом:
Введем замену
Выразим отсюда нашу одинокую неизвестную
Из этого следует, что какие бы
Аналогичным образом найдем
На этом наша система решений созрела — мы выразили абсолютно все неизвестные, не прибегая к делению, тем самым показывая, что решение точно будет целочисленным. Также не забываем, что
Таким образом, осталось ответить на вопрос — а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:
Для его решения в целых числах достаточно выполнение следующего условия:
(где
Доказательство
Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.
Резюмируя вышесказанное, выпишем алгоритм действий для решения линейных диофантовых уравнений с любым числом неизвестных:
- Проверяем, а решаемо ли уравнение вообще (вышеописанным свойством
). Если ответ положительный — переходим к следующему пункту.
- Для ускорения процесса поделим все коэффициенты (включая свободный член) на их
.
- Избавляемся от отрицательных коэффициентов в уравнении заменой
- Проводим серию замен (разваливая некоторые члены уравнения на суммы и объединяя их в скобки) таким образом, чтобы в конце концов один из членов уравнения был с единичным коэффициентов, и мы смогли вывести его без какого либо деления. Помня при этом, что за скобку можно взять только то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Наконец, объявляем все переменные, через которые выражена оная, как свободные.
- Выводим остальные переменные через вышевыведенную (выводим из всех наших замен), не забывая также про обратные замены.
- Объединяем все в единую систему решений.
В заключение стоит сказать, что также можно добавить ограничения на каждый член уравнения в виде неравенства на оного (тогда к системе решений добавляется система неравенств, в соответствии с которой нужно будет скорректировать ответ), а также добавить ещё чего-нибудь интересное. Ещё не стоит забывать и про то, что алгоритм решения является строгим и поддается записи в виде программы для ЭВМ.
С вами был Петр,
спасибо за внимание.