УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу МОДУЛЯРНАЯ АРИФМЕТИКА. Плохо обработанные заметки, и не уверен, что скоро вернусь к ним…


?

Найти двузначные натуральные числа, удовлетворяющие уравнению 17\, x+ 20\, y+45\, z =4111.

Решение. Выражаем x_{}:

x=241-y-2\,z+\frac{14-3\,y-11\,z}{17} \ .

Полагаем

17\, t_1 =14-3\,y-11\,z \quad \iff \quad 17\, t_1 + 3\,y+11\,z=14 \ .

Выражаем y_{}:

y=4-3\,z-5\,t_1+\frac{2-2\,z-2\,t_1}{3} \ .

Полагаем

3\, t_2=2-2\,z-2\,t_1 \quad \iff \quad 3\, t_2+2\,z+2\,t_1=2 \ .

Выражаем z_{}:

z=1-t_1-t_2-\frac{t_2}{2} \ .

Полагаем

t_2=2\,t_3 \ .

Теперь выражаем неизвестные x,y,z_{}:

z=1-t_1-3\,t_3,\ y=1-2\, t_1 +11\, t_3, x=238+5\, t_1- 5\, t_3 \ .

При любых значениях параметров \{t_1,t_3\} \subset \mathbb Z последние формулы дадут решение уравнения. Для того, чтобы удовлетворить дополнительным ограничениям на решения, параметры должны подчиняться условиям:

9< 238+ 5\, t_1- 5\, t_3 < 100, \ 9< 1-2\, t_1 +11\, t_3 < 100,\ 9< 1-t_1-3\,t_3 < 100\ .

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

-229<5(t_1- t_3)<-138,\ 8< -2\, t_1 +11\, t_3 < 99,\ 8< -t_1-3\,t_3 < 99 \ .

Разделим первое неравенство на 5_{} и воспользуемся предполагаемой целочисленностью параметров:

-46<t_1- t_3<-28,\ 8< -2\, t_1 +11\, t_3 < 99,\ 8< -t_1-3\,t_3 < 99 \ .

Прибавим первое неравенство к последнему:

-38<-4\,t_3<72 \qquad \Rightarrow \qquad 10>t_3>-18 \ ,

(здесь мы снова воспользовались целочисленностью параметра). Умножим теперь первое неравенство на 2_{} и прибавим ко второму:

-84<9\, t_3< 45 \qquad \Rightarrow \qquad -10<t_3<5 \ .

Именно последнее неравенство дает крайние значения для параметра t_{3}. Подставляя теперь в систему неравенств вместо t_{3} последовательно значения из множества \{-9,-8,\dots,3,4\}, получаем ограничения для t_{1}:

\begin{array}{r|l} t_3 & t_1 \\ \hline -9 &-54 \\ \hline -8 & -53,\, -52,\, -51,\,-50\,-49 \\ \hline -7 & -52, -51,\dots,-43 \\ \hline \vdots & \vdots \\ \hline 4 & -27,\,-26,\, -25 \end{array}

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

Ответ. (13,10,82), (13,19,78), (18,17,77), (78,11,57), (73,13,58), (33,\ 47,\ 58), \dots, (83,99,16).

Решение системы линейных уравнений в целых числах

Для решения системы линейных уравнений

\left\{ \begin{array}{lllll} a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &= b_1,\\ a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &= b_2,\\ \dots & & & \dots & \\ a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &= b_m \end{array} \right.

с целыми коэффициентами \{a_{jk} \}, \{b_j\} в целых числах x_1,x_2,\dots,x_n можно предложить следующий алгоритм. Выбираем произвольное уравнение с хотя бы одним ненулевым коэффициентом a_{jk}^{}, решаем его по приведенной ЗДЕСЬ схеме. Если это уравнение разрешимо в целых числах, то множество его решений записывается в виде соотношений

x_1=\beta_{11}t_1+\dots+\beta_{1,n-1}t_{n-1} + \gamma_1,\dots x_n=\beta_{n1}t_1+\dots+\beta_{n,n-1}t_{n-1} + \gamma_n,

при некоторых фиксированных целочисленных \{\beta_{jk} \}, \{\gamma_j\} и произвольном выборе целочисленных параметров t_1,\dots,t_{n-1}. Подставляем полученные соотношения в оставшиеся уравнения системы, переписываем их в новую систему — относительно новых неизвестных t_1,\dots,t_{n-1}. Число уравнений и число неизвестных уменьшились на единицу. Продолжаем процесс.

П

Пример. Решить систему линейных уравнений в целых числах

\left\{ \begin{array}{rrrrl} x_1& & - x_3 & +4\,x_4 &=3, \\ 2\,x_1 &- x_2 & & & =3, \\ 3\,x_1 &-2\,x_2 & & -x_4 & =1. \end{array} \right.

Решение. Из второго уравнения выражаем x_{2}:

x_2=-3+2\, x_1=t_1 \quad \Rightarrow \quad x_1=\frac{3+t_1}2=1+\frac{t_1+1}2 \ .

Обозначим

t_2=\frac{t_1+1}2 \quad \Rightarrow \quad x_1=1+t_2,\ \quad \Rightarrow \quad x_2=-1+2\,t_2 \ .

Подставляем в третье:

x_4=4-t_2 \ ,

теперь все получившиеся выражения для x_1,x_2,x_4 подставляем в первое уравнение:

x_3=14-3\,t_2 \ .

Ответ. x_1 = 1+t_2,\ x_2 =-1+2\,t_2,\ x_3=14-3\,t_2,\ x_4=4-t_2 при t_2 \in \mathbb Z.

Решим теперь более сложный пример.

П

Пример. Решить систему линейных уравнений в целых числах

\left\{ \begin{array}{rrrrl} 5\,x_1& + 7\, x_2 & +8\,x_3 &=11, \\ 2\,x_1 &- 3\,x_2 & +6\,x_3 & =5. \end{array} \right.

Решение. Имеем из первого уравнения:

x_1=\frac{11-7\,x_2-8\,x_3}{5}=2-x_2-x_3+\frac{1-2\,x_2-3\,x_3}{5} \quad \Rightarrow \quad t_1=\frac{1-2\,x_2-3\,x_3}{5} \ .

Далее,

2\,x_2+3\,x_3+5\,t_1=1 \quad \Rightarrow \quad x_2=\frac{1-3\,x_3-5\,t_1}{2}=-x_3-2\,t_1+ \frac{1-x_3-t_1}{2} \quad \Rightarrow \quad t_2=\frac{1-x_3-t_1}{2} \ .

Получаем выражение для x_{3}:

x_3=1-t_1-2\,t_2 \ ,

подставляем его в выражение для x_{2}:

x_2=-x_3-2\,t_1+t_2=-t_1=3\,t_2-1 \ .

Теперь

x_1=2-x_2-x_3+t_1=2+3\,t_1-t_2 \ .

Все три получившиеся формулы подставляем во второе уравнение системы:

3\,t_1-23\,t_2=-8 \ .

Решаем это уравнение в той же технике, получаем:

t_1=23\,u_2+5,\ t_2=3\, u_2+1 \ .

И возвращаемся к выражениям для x_1,x_2,x_3.

Ответ. x_1=16+66\, u_2,\ x_2=-3-14\, u_2,\ x_3=-6-29\, u_2 при u_2 \in \mathbb Z.

§

Если бы мы решали предыдущую систему в рациональных или вещественных числах, то получили бы аналогичный вид решения:

x_1=x_{10}+66\, t,\ x_2=x_{20}-14\, t,\ x_3=x_{30}-29\, t \quad npu \quad t \in \mathbb R \ .

Можно проверить, что сомножители при t_{} — это величины миноров системы уравнений, т.е.

\left| \begin{array}{ll} a_{12} & a_{13} \\ a_{22} & a_{23} \end{array} \right| , \quad -\left| \begin{array}{ll} a_{11} & a_{13} \\ a_{21} & a_{23} \end{array} \right| , \quad \left| \begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right|

соответственно. См. упражнение ЗДЕСЬ. Геометрически: направляющий вектор прямой, соответствующей пересечению двух плоскостей, всегда можно выбрать целочисленным. Таким образом, если система имеет целочисленное решение, то вхождения параметра в формулы, описывающие все множество этих решений, можно оценить с помощью методов линейной алгебры (см. теорию ЗДЕСЬ ). Проблема заключается в поиске хотя бы одного частного целочисленного решения x_{10},x_{20},x_{30}. Вот оно может и не существовать. К примеру, система

\left\{ \begin{array}{rrrrl} 2\,x_1& + x_2 & -x_3 &=1, \\ x_1 &+ 2\,x_2 & + x_3 & =1 \end{array} \right.

не имеет решений в \mathbb Z_{}.

§

Решение системы линейных уравнений в целых числах возможно еще симплекс-методом, но с этим я еще не разбирался. И следующий результат тоже выкладываю в надежде когда-нибудь разобраться…

Т

Теорема [Минковский]. Рассмотрим систему вещественных линейных неравенств относительно неизвестных x_{1},\dots,x_n

\left\{ \begin{array}{lllll} a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &\le b_1,\\ a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &\le b_2,\\ \dots & & & \dots & \\ a_{n1}x_1 &+a_{n2}x_2&+ \ldots&+a_{nn}x_n & \le b_n. \end{array} \right.

при b_1>0,b_2>0,\dots,b_n>0. Пусть определитель коэффициентов левых ее частей отличен от нуля:

\det [a_{jk}]_{j,k=1}^n \ne 0 \ .

Тогда система имеет целочисленное решение если произведение правых ее частей не меньше абсолютной величины этого определителя:

\prod_{j=1}^n b_j \ge \left| \det [a_{jk}]_{j,k=1}^n \right| \ .

Источник

Использованы материалы статьи

Cheema M.S. Integral solutions of a system of linear equations. The Amer.Math.Monthly. 1966, May, pp.487-490


2018/04/27 09:00 редактировал au