!!§!! Вспомогательная страница к разделу
☞
((:modular#общий_случай_линейного_уравнения МОДУЛЯРНАЯ АРИФМЕТИКА)). Плохо обработанные заметки, и не уверен, что скоро вернусь к ним...
==Решение системы линейных уравнений в целых числах==
Решение системы линейных уравнений
$$
\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 $ можно свести к случаю одного уравнения.
В
☞
((:modular#reshenie_linejnyx_sravnenij ПУНКТЕ)) полностью исследована задача решения линейного уравнения вида $ 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_{} $ и воспользуемся предполагаемой целочисленностью параметров:
$$-46t_3>-18 \ , $$
(здесь мы снова воспользовались целочисленностью параметра).
Умножим теперь первое неравенство на $ 2_{} $ и прибавим ко второму:
$$-84<9\, t_3< 45 \qquad \Rightarrow \qquad -10
☞