Занятие кружка « КВАНТ» Решение уравнений в целых числах.

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

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

xⁿ + yⁿ = zⁿ

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

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

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

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

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

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

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

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

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

• метод остатков;

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

1. Решить в целых числах уравнение x² – xy – 2y² = 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;

• б) 5х + 7у = 19;

• в) 201х – 1999у = 12.

• Решение

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

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

•  

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

• x₀ = 1, y₀ = 2.

• Тогда

• 5x₀ + 7y₀ = 19,

• откуда

• 5(х – x₀) + 7(у – y₀) = 0,

• 5(х – x₀) = –7(у – y₀).

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

• х – x₀ = 7k, у – y₀ = –5k.

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

• х = 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 – целое число.

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

• а) 20х + 12у = 2013;

• б) 5х + 7у = 19;

• в) 201х – 1999у = 12.

• Решение

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

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

•  

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

• x₀ = 1, y₀ = 2.

• Тогда

• 5x₀ + 7y₀ = 19,

• откуда

• 5(х – x₀) + 7(у – y₀) = 0,

• 5(х – x₀) = –7(у – y₀).

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

• х – x₀ = 7k, у – y₀ = –5k.

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

• х = 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³ + y³ = 3333333;

• б) x³ + y³ = 4(x²y + xy² + 1).

• Решение

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

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

•  

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

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

• 4. Решить

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

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

• Решение

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

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

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

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

• 2  х  16, 2  16.

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

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

•  

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

• x² – (y + 1)x + y² – y = 0. 

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

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

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

• Решение

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

• x² + 2y² = x³

• или, иначе,

• x²(x–1) = 2y².

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

• y = xn = n(2n²+1) = 2n³+n.

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

• Ответ: существует.

•  

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

• Решение

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

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

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

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

• x = 2x₁, y = 2y₁, z = 2z₁, u = 2u₁,

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

• x₁² + y₁² + z₁² + u₁² = 8x₁y₁z₁u₁.

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

• x₁ = 2x₂, y₁ = 2y₂, z₁ = 2z₂, u₁ = 2u₂,

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

• x₂² + y₂² + z₂² + u₂² = 32x₂y₂z₂u₂.

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

• Ответ: (0; 0; 0; 0).

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

• (х – у)³ + (y – z)³ + (z – x)³ = 30

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

• Решение

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

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

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

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

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

• abc = 10.

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

•  

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

• Решение

• Очевидно, что

• если х = 1, то у² = 1,

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

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

• х₁ = 1, у₁ = 1;

• х₂ = 1, у₂ = –1;

• х₃ = 3, у₃ = 3;

• х₄ = 3, у₄ = –3.

• Заметим, что при х = 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³ – b³ – c³ = 3abc,  a² = 2(b + c).

• Решение

• Так как

• 3abc 0, то a³  b³ + c³;

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

• b

• Складывая эти неравенства, получим, что

• b + c

• С учётом последнего неравенства, из второго уравнения системы получаем, что

• a² 

• Но второе уравнение системы также показывает, что а – чётное число. Таким образом, а = 2, b = c = 1.

• Ответ: (2; 1; 1)

•  

• 10. Найти все пары целых чисел х и у, удовлетворяющих уравнению х² + х = у⁴ + у³ + у² + у.

• Решение

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

• х(х + 1) = у(у + 1)(у² + 1),

• или

• х(х + 1) = (у² + у)(у² + 1)

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

• х₁ = 0, у₁ = 0;

• х₂ = 0, у₂ = –1;

• х₃ = –1, у₃ = 0;

• х₄ = –1, у₄ = –1.

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

• х₅ = 5, у₅ = 2;

• х₆ = –6, у₆ = 2.

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