Математика. Уравнения в целых числах. Примеры + решения.

Решение уравнений в целых числах является одной из древнейших математических задач. 

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

Теоремы о числе решений линейного диофантового уравнения

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

Теорема 1. Если в уравнении (ax + by) = 1,  (a,b) = 1, то уравнение имеет, по крайней мере, одно решение.

Теорема 2. Если в уравнении (ax + by) = с , (a,b) = d >1  и с не делится на d , то уравнение целых решений не имеет.

Теорема 3. Если в уравнении (ax + by) = с , (a,b) = d >1 , и  d⋮c, то оно равносильно уравнению (a₁x + b₁y) = 1 , в котором (a₁,b₁) = 1.

Теорема 4. Если в уравнении (ax + by) = 1, (a,b) = 1, то все целые решения этого уравнения заключены в формулах:

x = x₀c + bt

y = y₀c - at

где х₀ , у₀ – целое решение уравнения  (ax + by) = 1,  t- любое целое число.

Cформулируем на основании этих теорем алгоритм решения уравнения

Алгоритм решения уравнения в целых числах

Сформулированные теоремы позволяют составить следующий алгоритм решения в целых числах уравнения вида (ax + by) = с .

1. Найти наибольший общий делитель чисел a и b ,

если (a,b) = d >1  и с не делится на d , то уравнение целых решений не имеет;

если (a,b) = d >1  и  c⋮d , то переходим к этапу 2.

2. Разделить почленно уравнение (ax + by) = с  на d, получив при этом уравнение (a₁x + b₁y) = c₁ , в котором (a₁,b₁) = 1.

3. Найти целое решение (х₀ , у₀ ) уравнения (a₁x + b₁y) = 1 путем представления 1 как линейной комбинации чисел  a и b ;

4. Составить общую формулу целых решений данного уравнения

x = x₀c + bt

y = y₀c - at

где х₀ , у₀ – целое решение уравнения (ax + by) = 1, t- любое целое число.

Способы решения уравнений

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

1. Алгоритм Евклида.

2. Способ перебора вариантов.

3. Метод разложения на множители.

4. Метод остатков.

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

6. Цепные дроби.

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

Применение способов решения уравнений

Примеры решения уравнений.

Алгоритм Евклида.

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

а) 20х + 12у = 2013;

б) 5х + 7у = 19;

в) 201х – 1999у = 12.

Решение

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

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

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

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

в) 201х – 1999у = 12 Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 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 – целое число.

Решить уравнение в целых числах 407х – 2816y = 33.

Воспользуемся составленным алгоритмом.

1. Используя алгоритм Евклида, найдем наибольший общий делитель чисел 407 и 2816:

2816 = 407·6 + 374;

407 = 374·1 + 33;

374 = 33·11 + 11;

33 = 11·3

Следовательно (407,2816) = 11, причем 33 делится на 11

2. Разделим обе части первоначального уравнения на 11, получим уравнение 37х – 256y = 3, причем (37, 256) = 1

3. С помощью алгоритма Евклида найдем линейное представление числа 1 через числа 37 и 256.

256 = 37·6 + 34;

37 = 34·1 + 3;

34 = 3·11 + 1

Выразим 1 из последнего равенства, затем последовательно поднимаясь по равенствам будем выражать 3; 34 и полученные выражения подставим в выражение для 1.

1 = 34 – 3·11 = 34 – (37 – 34·1) ·11 = 34·12 – 37·11 = (256 – 37·6) ·12 – 37·11 =

– 83·37 – 256·(–12)

Таким образом, 37·(– 83) – 256·(–12) = 1, следовательно пара чисел х₀ = – 83 и у₀ = – 12 есть решение уравнения 37х – 256y = 3.

4. Запишем общую формулу решений первоначального уравнения

х = - 83с + bt = -83*3 - 256 t = -249 - 256t

y = -12c - at = -12*3 - 37t = -36 - 37t

где t - любое целое число.

2 Способ перебора вариантов.

Задача 2. В клетке сидят cобаки и кошки, всего у них 18 ног. Узнать, сколько в клетке тех и других?

Решение: Составляется уравнение с двумя неизвестными переменными, в котором х – число собак , у – число кошек:

4х + 2у = 18, или 2х + у = 9.

Выразим у через х : у = 9 – 2х.

Далее воспользуемся методом перебора:

х = 1__2__3__4__

у = 7__5__3__1__

Таким образом, задача имеет четыре решения.

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

3 Метод разложения на множители.

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

Задача 3. Решить уравнение в целых числах y³ - x³ = 91.

Решение. 1) Используя формулы сокращенного умножения, разложим правую часть уравнения на множители:

(y - x )(y² + xy + x² ) = 91

2) Выпишем все делители числа 91: ± 1; ± 7; ± 13; ± 91

3) Проводим исследование. Заметим, что для любых целых x и y число

y² + yx + x² ≥ y ² - 2|y ||x | + x ²= (|y | - |x |)² ≥ 0,

следовательно, оба сомножителя в левой части уравнения должны быть положительными. Тогда уравнение (y - x )(y² + xy + x² ) = 91 равносильно совокупности систем уравнений:

(у - х) = 1

(y² + xy + x² ) =91 

(у - х) = 91

(y² + xy + x² ) =1 

(у - х) = 7

(y² + xy + x² ) =13 

(у - х) = 13

(y² + xy + x² ) =7

4) Решив системы, получим: первая система имеет решения (5; 6), (-6; -5); третья (-3; 4),(-4;3); вторая и четвертая решений в целых числах не имеют.

Ответ: уравнение имеет четыре решения (5; 6); (-6; -5); (-3; 4); (-4;3).

Задача 4. Найти все пары натуральных чисел, удовлетворяющих уравнению

x² - у² = 69

Решение. Разложим левую часть уравнения на множители и запишем уравнение в виде

(х-у)(х +у) = 69

Т.к. делителями числа 69 являются числа 1, 3, 23 и 69, то 69 можно получить двумя способами: 69=1·69 и 69=3·23. Учитывая, что , получим две системы уравнений, решив которые мы сможем найти искомые числа:

Первая система имеет решение

(х - у) = 1

(х+у) = 69

х = 35, у = 34

 , а вторая система имеет решение .

(х - у) = 3

(х+у) = 23

х = 13 , у = 10

Ответ: (13;10) (35;34)  .

Задача 4. Найти все пары натуральных чисел, удовлетворяющих уравнению

x² - у² = 13

Решение. Разложим левую часть уравнения на множители и запишем уравнение в виде

(х-у)(х +у) = 13

Т.к. делителями числа 13 являются числа 1, и 13, то получим только одну систему уравнений:

(х - у) = 1

(х+у) = 13

х = 7, у = 6

Ответ: (7;6) 

Решить в целых числах уравнение 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).

Метод остатков

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

а) 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, то уравнение не имеет решений в целых числах.

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

Решить в целых числах уравнение 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).

ЕЩЕ УРАВНЕНИЯ)))

Сколько пар натуральных чисел удовлетворяет равенству 2x+5y=60?

Решение задачи

Так как (2x+5y)⋮5, то 2x⋮5, x⋮5. Аналогично можно показать, что y⋮2. Сделаем замену x=5x₀,y=2y₀. Тогда уравнение примет вид x₀+y₀ = 6. Очевидно, что это уравнение имеет в натуральных числах ровно 5 решений. Поэтому и исходное уравнение имеет ровно 5 решений.

Найдите количество целых решений уравнения xy + 6 = 2x + 3y, если x и y принадлежат отрезку [0;2014].

Перенесём все слагаемые в левую часть и разложим полученное выражение на множители:

xy + 6 = 2x+3y⇔xy − 2x−3y+6 = 0⇔ (x−3)(y−2) = 0.

Заметим, что, если x = 3, то y — любое, а если y = 2, то x — любое. (Так при умножении на 0 получается 0) Поэтому количество целых пар решений равно 2015 + 2015−1 = 4029.

Отметим, что решением исходного уравнения являются две прямые y=2 и x=3.

Найти все пары простых чисел x и y, удовлетворяющих уравнению:

x²−2y² = 1

В ответе запишите максимальное значение xx.

Решение задачи

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

x² = 1+ 2y²,

заключаем, что x — нечетное число. Теперь, приводя исходное уравнение к виду

(x−1)(x+1)=2y²,

заметим, что числа x−1 и x+1 четные, а из (x−1)(x+1)=2y²

следует, что y четное. Значит, y = 2 (это единственное простое четное число). Следовательно, x = 3.