Для решения системы линейных уравнений $$ \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