image

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


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

$5a+8b+3c+2d = 17$


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

$ \begin{cases}\displaystyle{ a= \frac{17-8b-3c-2d}{5}\\ b,c,d\in\mathbb{R} } \end{cases} $


где $\mathbb{R}$ — множество любых действительных чисел.

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

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

$ a,b,c,d \in \mathbb{Z} $


где $\mathbb{Z}$ — множество целых чисел.

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

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

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

$5a+8b+3c+2d = 17\\ \Leftrightarrow 5a+8b+2(c+d)+c = 17$


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

$c+d = t \Rightarrow \\5a+8b+2(c+d)+c = 17 \Leftrightarrow 5a+8b+2t+c = 17$


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

$5a+8b+2t+c = 17 \Leftrightarrow c = 17-5a-8b-2t$


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

Вспоминая, что $c+d = t$ справедливо говорить, что $d = t-c$. А подставив заместо $c$ полученный выше результат получим:

$d = t-c = t-(17-5a-8b-2t) = 3t+5a+8b-17$


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

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

$ \begin{cases}\displaystyle{ a,b,t \in \mathbb{Z}\\ c = 17-5a-8b-2t\\ d = 3t+5a+8b-17 } \end{cases} $


Теперь можно лицезреть, что в системе решений нигде нет деления, а это значит, что всегда решения будут целочисленными. Попробуем найти частное решение исходного уравнения, положив, к примеру, что $a=1;b=2;t=3$:

$ \begin{cases}\displaystyle{ a=1\\ b=2\\ t=3\\ c = 17-5\cdot1-8\cdot2-2\cdot3=-10\\ d = 3\cdot3+5\cdot1+8\cdot2-17=13 } \end{cases} $


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

$5\cdot1+8\cdot2+3\cdot(-10)+2\cdot13 = 17 \Leftrightarrow 17=17$


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

$3a+7b-11c=1$


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

$3a+7b+11c'=1$


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

$3a+7b+11c'=1 \Leftrightarrow 3(a+b)+4b+11c'=1$


Введем замену $a+b=t_1$, тогда получим:

$3(a+b)+4b+11c'=1 \Leftrightarrow 3t_1+4b+11c'=1$


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

$3t_1+4b+11c'=1 \Leftrightarrow 3(t_1+b)+b+11c'=1$


Введем замену $t_1+b=t_2$, тогда:

$3(t_1+b)+b+11c'=1 \Leftrightarrow 3t_2+b+11c'=1$


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

$3t_2+b+11c'=1 \Leftrightarrow b=1-11c'-3t_2$


Из этого следует, что какие бы $c',t_2$ мы не взяли, $b$ все равно останется целым числом. Тогда найдем $t_1$ из соотношения $t_1+b=t_2$:

$t_1+b=t_2 \Leftrightarrow t_1=t_2-b = t_2-(1-11c'-3t_2)\\ \Leftrightarrow t_1=4t_2+11c'-1$


Аналогичным образом найдем $a$ из соотношения $a+b=t_1$:

$a+b=t_1 \Leftrightarrow a=t_1-b = 4t_2+11c'-1 - (1-11c'-3t_2)\\ \Leftrightarrow a=7t_2+22c'-2$


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

$ \begin{cases}\displaystyle{ a=7t_2-22c-2\\ b=-3t_2+11c+1\\ c,t_2 \in \mathbb{Z} } \end{cases} $



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

$a_1b_1+a_2b_2+..+a_nb_n=N$


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

$N \mod GCD(a_1,a_2,..,a_n) = 0$


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


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

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

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

С вами был Петр,
спасибо за внимание.
Поделиться с друзьями
-->

Комментарии (10)


  1. chersanya
    10.06.2017 10:43
    +3

    Для его решения в целых числах необходимо выполнение следующего условия:
    N mod GCD(a1,a2,..,an)=0

    Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи.

    Можно же буквально одной фразой написать: все a_i делятся на GCD, поэтому вся левая часть уравнения делится на него — значит и правая должна делиться, чтобы было решение.


    1. ParadoxFilm
      10.06.2017 11:43
      +1

      Александр, добрый день.
      Это необходимое условие для доказательства, но не достаточное.
      Иными словами, из этого нет прямого следствия, что в таком случае решение будет (бесконечное множество решений).


      1. chersanya
        10.06.2017 13:55

        Да, это доказательство не достаточности, а необходимости — то есть именно процитированного утверждения из поста.


    1. ParadoxFilm
      10.06.2017 11:48

      Исправил формулировку в статье, чтобы не вводить в заблуждение по поводу достаточности и необходимости.


  1. GeMir
    10.06.2017 18:09
    -4

    Петр, без нарочито-весёлого стиля повествования («Так давайте выразим скорее! […] „не проканает“ […] Давайте и мы с вами её бахнем […] Опа […] Тождественно, круто!») статья не станет хуже.

    Ну и \cdot всё же. Вместо *. Спасибо.


    1. ParadoxFilm
      13.06.2017 07:59

      Георг, здравствуйте!
      Без искомого «нарочито-весёлого стиля повествования» статья не будет отличаться от сухого изложения из мат. учебников, я же пытаюсь хоть как-то внести жизнь и атмосферу в текст и вообще пообщаться с читателями, для меня это очень важно.
      По поводу \cdot вы совершенно правы, спасибо.


  1. ivlis
    11.06.2017 04:45

    Ого!


    1. Arastas
      11.06.2017 22:18

      Я, к сожалению, не очень хорошо читаю вольфрамовский и код. Что тут происходит и почему это "Ого"?


  1. rublag
    13.06.2017 07:52
    +1

    Есть более простой способ на сайте кафедры теории чисел мехмата МГУ.
    Кратко: для уравнения a_1*x_1+… + a_n * x_n = b строим матрицу из n+1 строк и n столбцов. Первая строка — коэффициенты при неизвестных в уравнении, оставшаяся часть — единичная матрица. Приводим матрицу к такому виду, что вся элементы первой строки нулевые за исключением первого, который равен НОД. преобразованиями столбцов: умножение столбца на -1, прибавление к стобцу любого другого, умноженного на целое число, умножение столбца на -1. Тогда элементы первой строки будут результатом подстановки соответствующих столбцов в выражение. А ответ — первый столбец, домноженный на b/НОД плюс остальные столбцы, домноженные на любые целые числа.


    1. ParadoxFilm
      13.06.2017 07:54

      Добрый день!
      Спасибо за метод, однако, едва ли он проще — нужно знать что такое м-цы и умение работать с оными (однако, можно просто заменить «школьным» видом СЛАУ). Да и сами преобразования по сложности примерно эквивалентны сложности в статье.