- PVSM.RU - https://www.pvsm.ru -
Здравствуйте, уважаемые читатели!
Продолжаю серию дилетантских статей о математике.
Сегодня предлагаю поразмышлять над некоторой интересной математической задачкой.
А именно, давайте-ка для разминки решим следующее линейной уравнение:
«Чего сложного?» — спросите вы. Действительно, лишь одно уравнение и целых четыре неизвестных. Следовательно, три переменных есть свободные, а последняя зависит от оных. Так давайте выразим скорее! Например, через переменную , тогда множество решений следующее:
где — множество любых действительных чисел.
Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.
Вспомним про линейные уравнения с целыми коэффициентами и целыми корнями, которые, собственно, являются разновидностью диофантовых уравнений [3]. Конкретно — наложим на наше уравнение соответствующие ограничение на целочисленность коэффициентов и корней. Коэффициенты при неизвестных у нас и так целые (), а вот сами неизвестные необходимо ограничить следующим:
где — множество целых чисел.
Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить как рациональное (дробное) число. Так как же решить это уравнение исключительно в целых числах?
Заинтересовавшихся решением данной задачи прошу под кат.
А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:
Задача выглядит по-прежнему непонятной, в таких случаях математики обычно производят какую-нибудь замену. Давайте и мы с вами её бахнем:
Опа, мы с вами достигли интересного результата! Коэффициент при у нас сейчас равен единице, а это значит, что мы с вами можем выразить эту неизвестную через остальные неизвестные в этом уравнении без всяких делений (чем грешили в самом начале статьи). Сделаем это:
Обращу внимание, что это говорит нам о том, что какие бы не были (в рамках диофантовых уравнений), всё равно останется целым числом, и это прекрасно.
Вспоминая, что справедливо говорить, что . А подставив заместо полученный выше результат получим:
Тут мы также видим, что что какие бы не были , всё равно останется целым числом, и это по-прежнему прекрасно.
Тогда в голову приходит гениальная идея: так давайте же объявим как свободные переменные, а будем выражать через них! На самом деле, мы уже это сделали. Осталось только записать ответ в систему решений:
Теперь можно лицезреть, что в системе решений нигде нет деления, а это значит, что всегда решения будут целочисленными. Попробуем найти частное решение исходного уравнения, положив, к примеру, что :
Подставим в исходное уравнение:
Тождественно, круто! Давайте попробуем ещё разок на другом примере?
Тут мы видим отрицательный коэффициент, он может доставить нам изрядных проблем, так что давайте от греха избавимся от него заменой , тогда уравнение будет следующим:
Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое — это брать числа которые самые близкие к единице:
Введем замену , тогда получим:
Вновь возьмем за скобку и наконец получим в уравнении неизвестную с единичным коэффициентом:
Введем замену , тогда:
Выразим отсюда нашу одинокую неизвестную :
Из этого следует, что какие бы мы не взяли, все равно останется целым числом. Тогда найдем из соотношения :
Аналогичным образом найдем из соотношения :
На этом наша система решений созрела — мы выразили абсолютно все неизвестные, не прибегая к делению, тем самым показывая, что решение точно будет целочисленным. Также не забываем, что , и нам надо ввести обратную замену. Тогда окончательная система решений следующая:
Таким образом, осталось ответить на вопрос — а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:
Для его решения в целых числах необходимо выполнение следующего условия:
(где — наибольший общий делитель [4]).
Резюмируя вышесказанное, выпишем алгоритм действий для решения линейных диофантовых уравнений с любым числом неизвестных:
В заключение стоит сказать, что также можно добавить ограничения на каждый член уравнения в виде неравенства на оного (тогда к системе решений добавляется система неравенств, в соответствии с которой нужно будет скорректировать ответ), а также добавить ещё чего-нибудь интересное.
С вами был Петр,
спасибо за внимание.
Автор: Петр Осетров
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/257549
Ссылки в тексте:
[1] Первая часть: https://habrahabr.ru/post/303740/
[2] Вторая часть: https://habrahabr.ru/post/319548/
[3] диофантовых уравнений: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BE%D1%84%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D0%BE_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5
[4] наибольший общий делитель: https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C
[5] Источник: https://habrahabr.ru/post/330632/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.