Решение линейных диофантовых уравнений с любым числом неизвестных +33
Математика
Рекомендация: подборка платных и бесплатных курсов создания сайтов - https://katalog-kursov.ru/
Здравствуйте, уважаемые читатели! Продолжаю серию дилетантских статей о математике.
Сегодня предлагаю поразмышлять над некоторой интересной математической задачкой.
А именно, давайте-ка для разминки решим следующее линейной уравнение:
«Чего сложного?» — спросите вы. Действительно, лишь одно уравнение и целых четыре неизвестных. Следовательно, три переменных есть свободные, а последняя зависит от оных. Так давайте выразим скорее! Например, через переменную
, тогда множество решений следующее:
где
— множество любых действительных чисел.
Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.
Вспомним про
линейные уравнения с целыми коэффициентами и целыми корнями, которые, собственно, являются разновидностью
диофантовых уравнений. Конкретно — наложим на наше уравнение соответствующие ограничение на целочисленность коэффициентов и корней. Коэффициенты при неизвестных у нас и так целые (
), а вот сами неизвестные необходимо ограничить следующим:
где
— множество целых чисел.
Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить
как рациональное (дробное) число. Так как же решить это уравнение
исключительно в целых числах?
Заинтересовавшихся решением данной задачи прошу под кат.
А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:
Задача выглядит по-прежнему непонятной, в таких случаях математики обычно производят какую-нибудь замену. Давайте и мы с вами её бахнем:
Опа, мы с вами достигли интересного результата! Коэффициент при
у нас сейчас
равен единице, а это значит, что мы с вами можем выразить эту неизвестную через остальные неизвестные в этом уравнении без всяких делений (чем грешили в самом начале статьи). Сделаем это:
Обращу внимание, что это говорит нам о том, что какие бы не были
(в рамках диофантовых уравнений), всё равно
останется целым числом, и это прекрасно.
Вспоминая, что
справедливо говорить, что
. А подставив заместо
полученный выше результат получим:
Тут мы также видим, что что какие бы не были
, всё равно
останется целым числом, и это по-прежнему прекрасно.
Тогда в голову приходит гениальная идея: так давайте же
объявим как свободные переменные, а
будем выражать через них! На самом деле, мы уже это сделали. Осталось только записать ответ в систему решений:
Теперь можно лицезреть, что в системе решений
нигде нет деления, а это значит, что всегда решения будут целочисленными. Попробуем найти частное решение исходного уравнения, положив, к примеру, что
:
Подставим в исходное уравнение:
Тождественно, круто! Давайте попробуем ещё разок на другом примере?
Тут мы видим отрицательный коэффициент, он может доставить нам изрядных проблем, так что давайте от греха избавимся от него заменой
, тогда уравнение будет следующим:
Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое — это брать коэффициенты из уравнения которые самые близкие к единице. Однако нужно понимать, что за скобку можно взять только лишь то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Итак:
Введем замену
, тогда получим:
Вновь возьмем за скобку и наконец получим в уравнении неизвестную с единичным коэффициентом:
Введем замену
, тогда:
Выразим отсюда нашу одинокую неизвестную
:
Из этого следует, что какие бы
мы не взяли,
все равно останется целым числом. Тогда найдем
из соотношения
:
Аналогичным образом найдем
из соотношения
:
На этом наша система решений созрела — мы выразили абсолютно все неизвестные, не прибегая к делению, тем самым показывая, что решение точно будет целочисленным. Также не забываем, что
, и нам надо ввести обратную замену. Тогда окончательная система решений следующая:
Таким образом, осталось ответить на вопрос — а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:
Для его решения в целых числах достаточно выполнение следующего условия:
(где
—
наибольший общий делитель).
ДоказательствоДоказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.
Резюмируя вышесказанное, выпишем алгоритм действий для решения линейных диофантовых уравнений с любым числом неизвестных:
- Проверяем, а решаемо ли уравнение вообще (вышеописанным свойством ). Если ответ положительный — переходим к следующему пункту.
- Для ускорения процесса поделим все коэффициенты (включая свободный член) на их .
- Избавляемся от отрицательных коэффициентов в уравнении заменой
- Проводим серию замен (разваливая некоторые члены уравнения на суммы и объединяя их в скобки) таким образом, чтобы в конце концов один из членов уравнения был с единичным коэффициентов, и мы смогли вывести его без какого либо деления. Помня при этом, что за скобку можно взять только то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Наконец, объявляем все переменные, через которые выражена оная, как свободные.
- Выводим остальные переменные через вышевыведенную (выводим из всех наших замен), не забывая также про обратные замены.
- Объединяем все в единую систему решений.
В заключение стоит сказать, что также можно добавить ограничения на каждый член уравнения в виде неравенства на оного (тогда к системе решений добавляется система неравенств, в соответствии с которой нужно будет скорректировать ответ), а также добавить ещё чего-нибудь интересное. Ещё не стоит забывать и про то, что алгоритм решения является строгим и поддается записи в виде программы для ЭВМ.
С вами был Петр,
спасибо за внимание.