Систему уравнений решить в целых числах уравнение

VMath

Инструменты сайта

Основное

Навигация

Информация

Действия

Указатель — Разделы — Обозначения — Автор — О проекте

Вспомогательная страница к разделу ☞ МОДУЛЯРНАЯ АРИФМЕТИКА. Плохо обработанные заметки, и не уверен, что скоро вернусь к ним…

Найти двузначные натуральные числа, удовлетворяющие уравнению $ 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 <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 \ . $$ При любых значениях параметров $ \ \subset \mathbb Z $ последние формулы дадут решение уравнения. Для того, чтобы удовлетворить дополнительным ограничениям на решения, параметры должны подчиняться условиям: $$ 9 t_3>-18 \ , $$ (здесь мы снова воспользовались целочисленностью параметра). Умножим теперь первое неравенство на $ 2_<> $ и прибавим ко второму: $$-84 ☞ ЗДЕСЬ схеме. Если это уравнение разрешимо в целых числах, то множество его решений записывается в виде соотношений $$ x_1=\beta_<11>t_1+\dots+\beta_<1,n-1>t_ + \gamma_1,\dots x_n=\beta_t_1+\dots+\beta_t_ + \gamma_n, $$ при некоторых фиксированных целочисленных $ \ <\beta_\>, \ <\gamma_j\>$ и произвольном выборе целочисленных параметров $ t_1,\dots,t_ $. Подставляем полученные соотношения в оставшиеся уравнения системы, переписываем их в новую систему — относительно новых неизвестных $ t_1,\dots,t_ $. Число уравнений и число неизвестных уменьшились на единицу. Продолжаем процесс.

Пример. Решить систему линейных уравнений в целых числах $$ \left\< \begin x_1& & — x_3 & +4\,x_4 &=3, \\ 2\,x_1 &- x_2 & & & =3, \\ 3\,x_1 &-2\,x_2 & & -x_4 & =1. \end \right. $$

Решение. Из второго уравнения выражаем $ x_ <2>$: $$x_2=-3+2\, x_1=t_1 \quad \Rightarrow \quad x_1=\frac<3+t_1>2=1+\frac2 \ . $$ Обозначим $$t_2=\frac2 \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 5\,x_1& + 7\, x_2 & +8\,x_3 &=11, \\ 2\,x_1 &- 3\,x_2 & +6\,x_3 & =5. \end \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 a_ <12>& a_ <13>\\ a_ <22>& a_ <23>\end \right| , \quad -\left| \begin a_ <11>& a_ <13>\\ a_ <21>& a_ <23>\end \right| , \quad \left| \begin a_ <11>& a_ <12>\\ a_ <21>& a_ <22>\end \right| $$ соответственно. См. упражнение ☞ ЗДЕСЬ. Геометрически: направляющий вектор прямой, соответствующей пересечению двух плоскостей, всегда можно выбрать целочисленным. Таким образом, если система имеет целочисленное решение, то вхождения параметра в формулы, описывающие все множество этих решений, можно оценить с помощью методов линейной алгебры (см. теорию ☞ ЗДЕСЬ ). Проблема заключается в поиске хотя бы одного частного целочисленного решения $ x_<10>,x_<20>,x_ <30>$. Вот оно может и не существовать. К примеру, система $$ \left\< \begin 2\,x_1& + x_2 & -x_3 &=1, \\ x_1 &+ 2\,x_2 & + x_3 & =1 \end \right. $$ не имеет решений в $ \mathbb Z_<> $.

Решение системы линейных уравнений в целых числах возможно еще симплекс-методом, но с этим я еще не разбирался. И следующий результат тоже выкладываю в надежде когда-нибудь разобраться…

Теорема [Минковский]. Рассмотрим систему вещественных линейных неравенств относительно неизвестных $ x_<1>,\dots,x_n $ $$ \left\< \begin 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_x_1 &+a_x_2&+ \ldots&+a_x_n & \le b_n. \end \right. $$ при $ b_1>0,b_2>0,\dots,b_n>0 $. Пусть определитель коэффициентов левых ее частей отличен от нуля: $$ \det [a_]_^n \ne 0 \ . $$ Тогда система имеет целочисленное решение если произведение правых ее частей не меньше абсолютной величины этого определителя: $$ \prod_^n b_j \ge \left| \det [a_]_^n \right| \ . $$

math4school.ru

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

Немного теории

Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского, который исследовал некоторые типы таких уравнений ещё до нашей эры.

Современной постановкой диофантовых задач мы обязаны французскому математику Ферма. Именно он поставил перед европейскими математиками вопрос о решении неопределённых уравнений только в целых числах. Наиболее известное уравнение в целых числах – великая теорема Ферма: уравнение

не имеет ненулевых рациональных решений для всех натуральных n > 2.

Теоретический интерес к уравнениям в целых числах достаточно велик, так как эти уравнения тесно связаны со многими проблемами теории чисел.

В 1970 году ленинградский математик Юрий Владимирович Матиясевич доказал, что общего способа, позволяющего за конечное число шагов решать в целых числах произвольные диофантовы уравнения, не существует и быть не может. Поэтому следует для разных типов уравнений выбирать собственные методы решения.

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

способ перебора вариантов;

применение алгоритма Евклида;

представление чисел в виде непрерывных (цепных) дробей;

разложения на множители;

решение уравнений в целых числах как квадратных (или иных) относительно какой-либо переменной;

метод бесконечного спуска.

Задачи с решениями

1. Решить в целых числах уравнение x 2 – xy – 2y 2 = 7.

Запишем уравнение в виде (x – 2y)(x + y) = 7.

Так как х, у – целые числа, то находим решения исходного уравнения, как решения следующих четырёх систем:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Решив эти системы, получаем решения уравнения: (3; –2), (5; 2), (–3; 2) и (–5; –2).

Ответ: (3; –2), (5; 2), (–3; 2), (–5; –2).

2. Решить в целых числах уравнение:

а) 20х + 12у = 2013;

в) 201х – 1999у = 12.

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

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

б) Подберём сначала некоторое конкретное решение. В данном случае, это просто, например,

Поскольку числа 5 и 7 взаимно простые, то

Значит, общее решение:

х = 1 + 7k, у = 2 – 5k,

где k – произвольное целое число.

Ответ: (1+7k; 2–5k), где k – целое число.

в) Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 1999 и 201:

НОД(1999, 201) = НОД(201, 190) = НОД(190, 11) = НОД(11, 3) = НОД(3 , 2) = НОД(2, 1) = 1.

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

1 = 2 – 1 = 2 – (3 – 2) = 2·2 – 3 = 2· (11 – 3·3) – 3 = 2·11 – 7·3 = 2·11 – 7(190 – 11·17) =

= 121·11 – 7·190 = 121(201 – 190) – 7·190 = 121·201 – 128·190 =

= 121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

Значит, пара (1273, 128) является решением уравнения 201х – 1999у = 1. Тогда пара чисел

x₀ = 1273·12 = 15276, y₀ = 128·12 = 1536

является решением уравнения 201х – 1999у = 12.

Общее решение этого уравнения запишется в виде

х = 15276 + 1999k, у = 1536 + 201k, где k – целое число,

или, после переобозначения (используем, что 15276 = 1283 + 7·1999, 1536 = 129 + 7·201),

х = 1283 + 1999n, у = 129 + 201n, где n – целое число.

Ответ: (1283+1999n, 129+201n), где n – целое число.

3. Решить в целых числах уравнение:

а) x 3 + y 3 = 3333333;

б) x 3 + y 3 = 4(x 2 y + xy 2 + 1).

а) Так как x 3 и y 3 при делении на 9 могут давать только остатки 0, 1 и 8 (смотрите таблицу в разделе «Делимость целых чисел и остатки»), то x 3 + y 3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

б) Перепишем исходное уравнение в виде (x + y) 3 = 7(x 2 y + xy 2 ) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

а) в простых числах уравнение х 2 – 7х – 144 = у 2 – 25у;

б) в целых числах уравнение x + y = x 2 – xy + y 2 .

а) Решим данное уравнение как квадратное относительно переменной у. Получим

у = х + 9 или у = 16 – х.

Поскольку при нечётном х число х + 9 является чётным, то единственной парой простых чисел, которая удовлетворяет первому равенству, является (2; 11).

Так как х, у – простые, то из равенства у = 16 – х имеем

С помощью перебора вариантов находим остальные решения: (3; 13), (5; 11), (11; 5), (13; 3).

Ответ: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

б) Рассмотрим данное уравнение как квадратное уравнение относительно x:

x 2 – (y + 1)x + y 2 – y = 0.

Дискриминант этого уравнения равен –3y 2 + 6y + 1. Он положителен лишь для следующих значений у: 0, 1, 2. Для каждого из этих значений из исходного уравнения получаем квадратное уравнение относительно х, которое легко решается.

Ответ: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Существует ли бесконечное число троек целых чисел x, y, z таких, что x 2 + y 2 + z 2 = x 3 + y 3 + z 3 ?

Попробуем подбирать такие тройки, где у = –z. Тогда y 3 и z 3 будут всегда взаимно уничтожаться, и наше уравнение будет иметь вид

Чтобы пара целых чисел (x; y) удовлетворяла этому условию, достаточно, чтобы число x–1 было удвоенным квадратом целого числа. Таких чисел бесконечно много, а именно, это все числа вида 2n 2 +1. Подставляя в x 2 (x–1) = 2y 2 такое число, после несложных преобразований получаем:

y = xn = n(2n 2 +1) = 2n 3 +n.

Все тройки, полученные таким образом, имеют вид (2n 2 +1; 2n 3 +n; –2n 3 – n).

6. Найдите такие целые числа x, y, z, u, что x 2 + y 2 + z 2 + u 2 = 2xyzu.

Число x 2 + y 2 + z 2 + u 2 чётно, поэтому среди чисел x, y, z, u чётное число нечётных чисел.

Если все четыре числа x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 делится на 4, но при этом 2xyzu не делится на 4 – несоответствие.

Если ровно два из чисел x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 не делится на 4, а 2xyzu делится на 4 – опять несоответствие.

Поэтому все числа x, y, z, u чётны. Тогда можно записать, что

и исходное уравнение примет вид

Теперь заметим, что (2k + 1) 2 = 4k(k + 1) + 1 при делении на 8 даёт остаток 1. Поэтому если все числа x₁, y₁, z₁, u₁ нечётны, то x₁ 2 + y₁ 2 + z₁ 2 + u₁ 2 не делится на 8. А если ровно два из этих чисел нечётно, то x₁ 2 + y₁ 2 + z₁ 2 + u₁ 2 не делится даже на 4. Значит,

и мы получаем уравнение

Снова повторив те же самые рассуждения, получим, что x, y, z, u делятся на 2 n при всех натуральных n, что возможно лишь при x = y = z = u = 0.

7. Докажите, что уравнение

(х – у) 3 + (y – z) 3 + (z – x) 3 = 30

не имеет решений в целых числах.

Воспользуемся следующим тождеством:

(х – у) 3 + (y – z) 3 + (z – x) 3 = 3(х – у)(y – z)(z – x).

Тогда исходное уравнение можно записать в виде

(х – у)(y – z)(z – x) = 10.

Обозначим a = x – y, b = y – z, c = z – x и запишем полученное равенство в виде

Кроме того очевидно, a + b + c = 0. Легко убедиться, что с точностью до перестановки из равенства abc = 10 следует, что числа |a|, |b|, |c| равны либо 1, 2, 5, либо 1, 1, 10. Но во всех этих случаях при любом выборе знаков a, b, c сумма a + b + c отлична от нуля. Таким образом, исходное уравнение не имеет решений в целых числах.

8. Решить в целых числах уравнение 1! + 2! + . . . + х! = у 2 .

если х = 1, то у 2 = 1,

если х = 3, то у 2 = 9.

Этим случаям соответствуют следующие пары чисел:

Заметим, что при х = 2 имеем 1! + 2! = 3, при х = 4 имеем 1! + 2! + 3! + 4! = 33 и ни 3, ни 33 не являются квадратами целых чисел. Если же х > 5, то, так как

5! + 6! + . . . + х! = 10n,

можем записать, что

1! + 2! + 3! + 4! + 5! + . . . + х! = 33 + 10n.

Так как 33 + 10n – число, оканчивающееся цифрой 3, то оно не является квадратом целого числа.

Ответ: (1; 1), (1; –1), (3; 3), (3; –3).

9. Решите следующую систему уравнений в натуральных числах:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0, то a 3 > b 3 + c 3 ;

таким образом имеем

b 2 2 + х = у 4 + у 3 + у 2 + у.

Разложив на множители обе части данного уравнения, получим:

х(х + 1) = у(у + 1)(у 2 + 1),

х(х + 1) = (у 2 + у)(у 2 + 1)

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

Произведение (у 2 + у)(у 2 + 1) можно рассматривать как произведение двух последовательных целых чисел, отличных от нуля, только при у = 2. Поэтому х(х + 1) = 30, откуда х₅ = 5, х₆ = –6. Значит, существуют ещё две пары целых чисел, удовлетворяющих исходному уравнению:

Ответ: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Задачи без решений

1. Решить в целых числах уравнение:

б) х 2 + у 2 = х + у + 2.

2. Решить в целых числах уравнение:

а) х 3 + 21у 2 + 5 = 0;

б) 15х 2 – 7у 2 = 9.

3. Решить в натуральных числах уравнение:

4. Доказать, что уравнение х 3 + 3у 3 + 9z 3 = 9xyz в рациональных числах имеет единственное решение

5. Доказать, что уравнение х 2 + 5 = у 3 в целых числах не имеет решений.

8. Базовая математика Читать 0 мин.

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

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

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

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

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

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

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

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

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

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

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

Методом перебора находим решение $ x_1=2;\;y_1=3. $

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

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

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

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

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

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

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

НОД (5, 7) = НОД (5, 7-5) = НОД (5, 2) = НОД (5 — 2∙2, 2) = НОД (1, 2) = 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вернёмся к нашему уравнению $ \ 3^+4^=5^ $

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

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

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

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

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

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

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

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

$ \ 5^+2^-(5^-2^)=2\cdot 2^ $ — это число никогда не будет кратно 3. Значит, в нашем произведении один из множителей равен 1, а другой равен 3 2n . Так как $ \ 5^+2^> 1 $ ,

$ \ 5^-2^=1,5^+2^)=3^ <2n>$ Итак, мы с вами уже решаем немного другое уравнение, с переменными m и n, которые зависят от х и у. И пришли к выводу, что $ \ 5^+2^=1 $

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