Уравнения в целых числах

Уравнения целых чисел

Также такие уравнения называются диофантовыми, в честь древнегреческого математика Диофанта Александрийского, который изучал такие уравнения еще до нашей эры.

При решении уравнений в целых и натуральных числах можно выделить следующие способы.

1 способ. Метод перебора вариантов.

Решим уравнение $\left( x - 2 \right)\left( y + 3 \right) = 4$ в целых числах.

Так как x и у целые числа, совершим перебор вариантов:

$x - 2 = 1;y + 3 = 4$ $\rightarrow x = 3;y = 1$

$x - 2 = 4;y + 3 = 1$ $\rightarrow x = 6;y = - 2$

$x - 2 = - 1;y + 3 = - 4$ $\rightarrow x = 1;y = - 7$

$x - 2 = - 4;y + 3 = - 1$ $\rightarrow x = - 2;y = - 4$

$x - 2 = 2;y + 3 = 2$ $\rightarrow x = 4;y = - 1$

$x - 2 = - 2;y + 3 = - 2$ $\rightarrow x = 0;y = - 5$

Ответ: (3; 1), (6; -2), (1; -7), (-2; -4), (4; -1), (0; -5).

Решим уравнение $10x\ + \ 10y\ = \ 2019$ в целых числах.

Поскольку при любых целых значениях х и у левая часть уравнения делится на два, а правая является нечётным числом, то уравнение не имеет решений в целых числах.

Ответ: решений нет.

Пусть нужно решить уравнение в целых числах: $5x + 4y = 22$.

Методом перебора находим решение $x_{1} = 2;y_{1} = 3$.

Получаем систему уравнений:

$\left\{ \begin{matrix} 5x + 4y = 22 \\ 5 \bullet 2 + 4 \bullet 3 = 22 \\ \end{matrix} \right.\ \$

$5\left( x - 2 \right) + 4\left( y - 3 \right) = 0$

$5\left( x - 2 \right) = - 4\left( y - 3 \right)$

$x - 2 = \frac{- 4\left( y - 3 \right)}{5}$

Из полученного равенства видно, что число $(x - 2)$ будет целым тогда и только тогда, когда $(y - 3)$ делится на 5, т.е. $y - 3 = 5n$, где n какое-нибудь целое число.

Имеем:

$y = 3 + 5n$

$x - 2 = - 4 \bullet \frac{5n}{5} = - 4n$

$x = 2 - 4n$

Тем самым все целые решения исходного уравнения можно записать в таком виде:

($2 - 4n;3 + 5n)$, где $n \in Z$.

Ответ: ($2 - 4n;3 + 5n)$, где $n \in Z$.

2 способ. Алгоритм Евклида

Пусть нужно решить уравнение в целых числах: $5x + 7y = 6$.

Сделаем это с помощью Алгоритма Евклида. Ищем НОД чисел 5 и 7 с помощью него:

$НОД\ (5,\ 7) = НОД\ (5,\ 7 - 5) = НОД\ (5,\ 2) = НОД\ (5\ - \ 2 \bullet 2,\ 2) = НОД\ (1,\ 2) = 1$

Запишем этот процесс в обратном порядке:

$1 = 2 - 1 = 2 - \left( 5 - 2 \bullet 2 \right) = 2 \bullet 3 - 5 \bullet 1 = \left( 7 - 5 \right) \bullet 3 - 5 \bullet 1 = 7 \bullet 3 - 5 \bullet 4$

То есть:

$1 = 5 \bullet \left( - 4 \right) + 7 \bullet 3$

Тогда:

$1 \bullet 6 = 5 \bullet \left( - 4 \right) \bullet 6 + 7 \bullet 3 \bullet 6$

$6 = 5 \bullet \left( - 24 \right) + 7 \bullet 18$

$6 = 5x + 7y$

Тогда $x = - 24$ и $y = 18$ является решением уравнения.

Общее решение записывается в виде:

$x = - 24 + 7n;y = 18 + 5n$, где n – любое целое число.

Выполним проверку:

$5\left( - 24 + 7n \right) + 7\left( 18 + 5n \right) = 6$

$- 120 + 35n + 126 + 35n = 6$

$70n = 0$

$n$ – любое целое.

Верно.

Это не всевозможные способы решения. Зачастую для решения диофантовых уравнений требуются более тонкие рассуждения, связанные с делимостью, перебором остатков, оценками частей уравнения, тождественными преобразованиями и т.п.

Решим уравнение:

$3^{x} + 4^{y} = 5^{z}$

Разложить на множители и выразить переменную мы здесь не можем. Воспользуемся методом перебора остатков.

Если левая часть уравнения в целых числах кратна какому-то числу, то и другая обязательно должна быть кратна этому же числу. Отсюда следует, что и остатки от деления обеих частей уравнения на одно и то же число будут давать одинаковые остатки.

Будем делать выводы о делимости одной части уравнения на какое-либо число (или смотреть, какой остаток от деления при этом получается) и проверять, при каких значениях переменных вторая часть уравнения также делится на это число (либо даёт такой же остаток).

Левая часть кратна 5. И остатки от деления на 5 у обеих частей также будут равны.

Про пятёрку уже сказали, что правая часть делится на неё без остатка, значит и левая тоже должна делиться.

Рассмотрим остатки от деления на 4.

z	$5^{z}$	Остаток при делении на 4
1	5	1
2	25	1
3	125	1
4	625	1

Видим простую закономерность, что 5 в любой степени при делении на 4 будет давать остаток 1.

Теперь левая часть: $4^{у}$ будет делиться на 4 без остатка.

Рассмотрим остатки от деления на 4 числа $\ 3^{x}$.

х	$3^{x}$	Остаток при делении на 4
1	3	3
2	9	1
3	27	3
4	81	1
5	243	3

И так далее. Закономерность: при чётных х остаток 1, при нечётных остаток 3.

Отсюда делаем вывод, что х - число чётное, значит, мы можем представить его как х=2n.

Теперь рассмотрим остатки при делении обеих частей на 3.

Правая часть:

z	$5^{z}$	Остаток при делении на 3
1	5	2
2	25	1
3	125	2
4	625	1

И так далее. Видим закономерность, что при чётных z остаток равен 1, при нечетных z остаток равен 2.

Рассмотрим левую часть. Число $3^{x}$ даёт остаток 0 при делении на 3.

Рассмотрим остатки от деления на 3 числа$\ 4^{y}$:

y	$4^{y}$	Остаток при делении на 3
1	4	1
2	16	1
3	64	1
4	256	1
5	1024	1

Получается, что левая часть при делении на 3 может давать только остаток 1. Значит, и правая тоже. Это происходит при чётных z.

Вернёмся к нашему уравнению $3^{x} + 4^{y} = 5^{z}$ .

Рассмотрев все остатки от деления, мы делаем выводы, что х и z - чётные числа. Тогда х=2n, z=2m, где m, n натуральные. Подставим в уравнение:

$3^{2n} + 4^{y} = 5^{2m}$ , заметим также, что$\ 4^{y} = 2^{2y}$

Теперь мы можем разложить на множители, используя формулу разности квадратов:

$2^{2у}\ = \ 5^{2m}\ - \ 3^{2n}\$

$\left( 5^{m}\ - \ 3^{n} \right)\left( 5^{m}\ + \ 3^{n} \right) = \ 2^{2у}$. Получается, что обе скобки должны быть степенями двойки. Мы не можем сделать никаких обоснованных выводов. Наша группировка неудачная. Попробуем иначе:

$5^{2m}\ - \ 2^{2у}\ = \ 3^{2n}\$

$(5^{m}\ - \ 2^{у})\ (5^{m}\ + \ 2^{у})\ = \ 3^{2n}$

Теперь у нас обе скобки являются произведением троек. Рассмотрим такую ситуацию,

$а \bullet b = 3^{2n}$, это означает, что и а, и b кратны 3. Либо одно из чисел кратно 3, а другое равно 1.

Рассмотрим случай, когда и а, и b кратны трём. Вспомним основные свойства делимости.

Ключевым признаком здесь будет второй: в нашем случае разность a-b также будет делиться на 3.

Рассмотрим разность скобок:

$5^{m} + 2^{y} - \left( 5^{m} - 2^{y} \right) = 2 \bullet 2^{y}$ — это число никогда не будет кратно 3. Значит, в нашем произведении один из множителей равен 1, а другой равен 3²ⁿ. Так как $5^{m} + 2^{y} > 1$,

$5^{m} - 2^{y} = 1$, $5^{m} + 2^{y}$ $= \ 3^{2n}$.

Итак, мы с вами уже решаем немного другое уравнение, с переменными m и n, которые зависят от х и у. И пришли к выводу, что $5^{m} - 2^{y} = 1$.

Рассмотрим степени пятёрки и двойки:

m	$5^{m}$	y	$2^{y}$
0	1	0	1
1	5	1	2
2	25	2	4
3	125	3	8

Эта таблица показывает, что $5^{m} - 2^{y} = 1$ только в одном случае при $m = 1,\ y = 2$. При их увеличении разница между $5^{m}$ и $2^{у}$ будет всё больше, поэтому это единственное решение.

Тогда $z = 2m = 2,\ x = 2.$

Ответ: (2, 2, 2)