Указатель — Разделы — Обозначения — Автор — О проекте
Вспомогательная страница к разделу ☞ МОДУЛЯРНАЯ АРИФМЕТИКА. Плохо обработанные заметки, и не уверен, что скоро вернусь к ним…
Найти двузначные натуральные числа, удовлетворяющие уравнению $ 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)\leftarrow138,\ 8< -2\, t_1 +11\, t_3 < 99,\ 8< -t_1-3\,t_3 < 99 \ . $$
Разделим первое неравенство на $ 5_{} $ и воспользуемся предполагаемой целочисленностью параметров:
$$-46<t_1- t_3\leftarrow28,\ 8< -2\, t_1 +11\, t_3 < 99,\ 8< -t_1-3\,t_3 < 99 \ . $$
Прибавим первое неравенство к последнему:
$$-38\leftarrow4\,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