Решение системы линейных уравнений $$ \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_1x+A_2y=B $ относительно двух неизвестных $ x_{} $ и $ y_{} $. Теперь организуем переход к случаю одного уравнения с $ n>2 $ неизвестными.

Теорема. Уравнение

$$ A_1x_1+A_2x_2+\dots+A_nx_n=B \quad npu \quad \{A_1,A_2,\dots,A_n,B\} \subset \mathbb Z, n\ge 2, \exists A_j \ne 0 $$

имеет решение тогда и только тогда, когда $ B_{} $ делится на $ d=\operatorname{HOD} (A_1,A_2,\dots,A_n) $.

Доказательство. Необходимость. Все числа $ A_1,A_2,\dots,A_n $ делятся на $ d_{} $, следовательно и сумма $ A_1x_1+A_2x_2+\dots+A_nx_n $ делится на $ d_{} $. Значит и число $ B_{} $ должно делиться на $ d_{} $. ♦

Пример 1 [3]. Решить уравнение $ 10\,x+9\,y+7\,z=58 $.

Решение. Выразим из этого уравнения неизвестную при минимальном (по абсолютной величине) коэффициенте: $$ z=\frac{58-10\,x-9\,y}{7}=8-x-y+\frac{2-3\,x-2\,y}{7} \ . $$ Поскольку, по предположению, все неизвестные должны быть числами целыми, то положим $$\frac{2-3\,x-2\,y}{7}=u_1 \quad \mbox{ или } \quad 2-3\,x-2\,y=7\, u_1 \ . $$ Теперь выразим из этого уравнения неизвестную при минимальном (по абсолютной величине) коэффициенте: $$ y = \frac{2-3\,x-7\, u_1}{2}= 1- x-3\, u_1- \frac{x+u_1}{2} \ . $$ Положим $$ \frac{x+u_1}{2}=u_2 \quad \mbox{ или } \quad x=2\,u_2-u_1 \ . $$ Подставим найденное выражение в предыдущее выражение для $ y_{} $: $$ y=1-x-3\,u_1-u_2=1-(2\,u_2-u_1)-3\,u_1-u_2=1-2\,u_1-3\,u_2 \ ; $$ и, окончательно, в выражение для $ z_{} $: $$ z=8-(2\,u_2-u_1)-(1-2\,u_1-3\,u_2)+u_1=7+4\,u_1+u_2 \ . $$ Таким образом, значения неизвестных $ x,y,z $ полностью определяются формулами $$ x=-u_1+2\,u_2,\ y=1-2\,u_1-3\,u_2,\ z=7+4\,u_1+u_2 \quad npu \quad \{u_1,u_2\} \subset \mathbb Z \ . $$ Если поставить дополнительное требование положительности решений, то получаем условия на параметры $ u_1,u_2 $ в виде неравенств $$ -u_1+2\,u_2>0 ,\ 1-2\,u_1-3\,u_2 > 0,\ 7+4\,u_1+u_2 > 0 \ . $$ Разрешим каждое из этих неравенств относительно $ u_{1} $: $$ u_1<2\,u_2, \ u_1 < \frac{1-3\,u_2}{2},\ u_1>\frac{-7-u_2}{4} \ . $$ Объединяя первое неравенство с третьим и второе неравенство с третьим, получаем ограничения на $ u_{2} $: $$ \frac{-7-u_2}{4}< 2\,u_2, \ \frac{-7-u_2}{4}< \frac{1-3\,u_2}{2} , $$ откуда: $$ -7/9 < u_2 < 9/5 \ . $$ Поскольку, по предположению, $ u_{2} $ — целое, то $ u_2\in \{0,1\} $. Подставляем $ u_2=0 $ в систему неравенств относительно $ u_{1} $: $$ u_1<0,\ u_1<\frac{1}{2},\ u_1>-\frac{7}{4} \qquad \Rightarrow \qquad u_1=-1 \ . $$ Подставляем $ u_2=1 $ в систему неравенств относительно $ u_{1} $: $$u_1<2,\ u_1< -1,\ u_1>-2 \ . $$ Эта система неравенств не имеет целых решений. Таким образом, положительные решения исходного сравнения получаются только при значениях параметров $ u_1=-1,u_2=0 $: $$ x=1,\ y=3, \ z=3 \ . $$ ♦

Пример 2. Найти двузначные натуральные числа, удовлетворяющие уравнению

$$ 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\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}^{} $, решаем его по приведенному в предыдущем пункте алгоритму. Если это уравнение разрешимо в целых числах, то множество его решений записывается в виде соотношений $$ 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} $. Число уравнений и число неизвестных уменьшились на единицу. Продолжаем процесс.

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

$$ \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 $.

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

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

$$ \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 $.

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

$$ 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_{} $.

Можно осуществить предварительное преобразование системы к эквивалентному виду по методу Гаусса. Прямой ход этого метода приведет¹⁾ систему к виду когда каждое следующее уравнение будет зависеть от меньшего числа переменных нежели предыдущее. Хотя при этом полученные уравнения будут иметь, в общем случае, рациональные коэффициенты, мы сможем вернуться к целочисленному случаю домножением этих уравнений на подходящие целые числа. Если получившаяся система имеет треугольный вид, то решение ее единственно и представимо в рациональных числах. Остается только надеяться, что эти числа окажутся целыми (что всегда произойдет, к примеру, в случае $ m=n $ и при $ \det A= 1 $). Если же последнее уравнение полученной системы зависит от более чем одной переменной, то применяем к нему алгоритм из предыдущего пункта, и, в случае удачи (существования целочисленных решений) идем обратным ходом метода Гаусса. На каждом шаге придется устанавливать разрешимость очередного линейного уравнения (полученного подстановкой общего решения предыдущего) в целых числах.

Теорема [Минковский]. Рассмотрим систему вещественных линейных неравенств относительно неизвестных $ 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| \ . $$

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

[2]. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М. Мир. 1977, С.368-369.

[3]. Малининъ А., Буренинъ К. Руководство алгебры и собранiе алгебраическихъ задачъ для гимназiй, реальныхъ училищъ и учительскихъ институтовъ. Изданiе седьмое. М. Издание книжнаго магазина наследников бр. Салаевыхъ. 1884.