Неопределенные уравнения

Неопределенные уравнения

Средняя школа №12 г. Новополоцка

Методическое объединение математики

1) - переменные принимают целые значения . " width="640"

Определение

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

или

• Диофа́нтово уравнение — это уравнение вида

где P — целочисленная функция (например, полином с целыми коэффициентами), х 1 , х 2 , …,х т (т1) - переменные принимают целые значения .

История (очень кратко)

Диофант

(3 век н.э.)

Юрий Матиясевич

(1730 г)

Пьер Ферма

Эндрю Уайлс

(1730 г)

(1995 г)

Брахмагупта

(625 г н.э.)

1 и с не делится на d, то уравнение целых решений не имеет. Теорема . Если в уравнении ах + by = с , НОД( а, b ) = 1, то все целые решения этого уравнения заключены в формулах: где x 0 , y 0 – целое решение уравнения ах + by = 1 , t – любое целое число. " width="640"

Линейные диофантовы уравнения

Уравнения вида ax + by = c , где a, b, c – целые числа, отличные от нуля.

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

Теорема . Если в уравнении ах + by = с , НОД( а, b ) = 1, то все целые

решения этого уравнения заключены в формулах:

где x 0 , y 0 – целое решение уравнения ах + by = 1 , t – любое целое число.

Линейные диофантовы уравнения

Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах + by = с, где НОД(а, b) = 1:

1) находится целое решение (х 0 ;у 0 ) уравнения ах + by = 1 путем представления 1 как линейной комбинации чисел а и b (для этого может применяться , например, алгоритм Евклида)

2) составляется общая формула целых решений данного уравнения:

Линейные диофантовы уравнения

Пример 1 . Найти целые решения уравнения 407х – 2816у = 33.

Решение

НОД(407,2816,33)=11, поэтому приведем уравнение к виду 37х – 256у = 3

1 ) Решим уравнение 37x – 256y = 1. Применим алгоритм Евклида :

256:37=6(ост 34)

37:34=1(ост 3)

34:3=11(ост 1), поэтому

1=34-11·3=34-11·(37-34·1)=34·12-37·11=(256-37·6)·12-37·11=256·12-37·83,

37·(-83)-256·(-12) = 1 – линейная комбинация, т. е.

2) Найдем решения по формулам

Получим

.

Линейные диофантовы уравнения

Пример 2 . Найти наибольшее трехзначное число, которое при делении на 17 дает остаток 9, а при делении на 22 дает остаток 4.

Решение (сложное)

Пусть частное от деления числа на 17 равно x, тогда искомое число равно: 17x + 9.

Пусть частное от деления числа на 22 равно y, тогда искомое число равно: 22y + 4

По условию: 17x + 9 = 22y + 4, 22y – 17x = 5 – неопределенное уравнение.

1) Решим уравнение: -17x + 22y = 1. Применим метод цепных дробей

Отбросив последнее звено цепной дроби получим

Найдем разность т.е. 22·7-17·9=1, х 0 =9, у 0 =7.

2) Тогда х=5·9+22t,

Наибольшее трехзначное число 774 получается при t=0. Ответ: 774

Линейные диофантовы уравнения

Пример 2 . Найти наибольшее трехзначное число, которое при делении на 17 дает остаток 9, а при делении на 22 дает остаток 4.

Решение (простое)

Пусть частное от деления числа на 17 равно x, тогда искомое число равно: 17x + 9.

Пусть частное от деления числа на 22 равно y, тогда искомое число равно: 22y + 4

По условию: 17x + 9 = 22y + 4, 22y – 17x = 5 – это неопределенное уравнение.

Решим уравнение методом подбора.

Легко заметить, что (1;1) – решение уравнения, поэтому общее решение может быть записано в виде х=1+22t, y=1+17t,

Наибольшее трехзначное число 774 получается при t=2. Ответ: 774

Нелинейные диофантовы уравнения Метод разложения на множители

Пример 3 . Найти целые решения уравнения .

Решение

Преобразуем уравнение ,

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

Получим или

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

Нелинейные диофантовы уравнения метод разложения на множители

n²+n=m²+2m-9

Решение

Умножив данное равенство на 4 получим равносильное равенство

Поэтому рассмотрим 8 случаев: 1) 2)

Нелинейные диофантовы уравнения метод разложения на множители

Пример 4 . (продолжение)

• 4) 5) 6)

7) 8)

Решив полученные системы, найдем решения уравнения.

Ответ: (-10;-11), (-10;9), (-3;-5),(-3;-3), (2;-5),(2;3),(9;9), (9;-11)

Нелинейные диофантовы уравнения метод, основанный на выделении целой части дроби

Пример 5. Решить уравнение в целых числах х 2 -ху+5х-9=0

Решение.

х 2 +5х-9

9

,

b) Z, если х= ±1, ±3, ±9

х=-1, у=13 х=3, у=5

х=1, у=-3, х=-9, у=-3

х=-3, у=5 х=9, у=13

Ответ(-1;13);(1;-3);(-3;5);(3;5);(-9;-3);(9;13).

у =

х+5

=

-

, у Z

x

x

9

x

Нелинейные диофантовы уравнения метод выделения полного квадрата

Пример 6. Найти все целочисленные решения

Решение.

Значит, у=0;

Ответ: (2;-1), (-2;1),(8;1),(-8;-1)

Нелинейные диофантовы уравнения метод решения уравнения как квадратного относительно одной из переменных

Пример 7. Решить уравнение в целых числах 10х+у=х 2 +у 2+ 13

Решение :

10х+у=х 2 +у 2 -13

х 2 -10х+у 2 -у+13=0

D/4=25-y 2 +y-13

Уравнение имеет корни при D/4≥0, т.е.

D/4=25-у 2 +у-13 ≥0

-у 2 +у+12 ≥0

у 2 -у-12≤0

т.е. -3 ≤у ≤4, т.о. переберем все возможные значения :

у=4, 3, 2, 1,0,-1,-2,-3 и получим ответ

ОТВЕТ: (-5;-3), (5;4)

Нелинейные диофантовы уравнения метод , основанный на оценке выражений, входящих в уравнение

Пример 8 . Решить в целых числах уравнение

Решение:

1) Заметим, что слагаемые в левой части уравнения имеют одинаковый знак, а поскольку их сумма положительна, то каждое слагаемое также положительно. Поэтому к сумме, стоящей слева, применим неравенство Коши:

Откуда, xyz = 1.

2) Исследуем возможные наборы трех целых чисел, которые в

произведении дают 1. Это могут быть тройки (1,1,1), (1,-1,-1), (-1,-1,1),(-1,1,-1).

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

Ответ: (1,1,1); (1,-1,-1); (-1,-1,1); (-1,1,-1).

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

Пример 9. Решить в целых числах

Решение.

Ответ : (2; 0)

Нелинейные диофантовы уравнения с помощью учета свойств делимости и остатков

Пример 10. (Третий этап олимпиады, 2011г, 8 класс)

Существуют ли решения уравнения в целых числах

Решение.

1) Так как - четное, 2011- нечетное, то у- нечетное.

2) Значит, оканчивается на 5, а оканчивается на 6.

3) Поэтому оканчивается на 6, и оканчивается на 3 или на 8.

Но квадраты чисел не могут оканчиваться на 3 или на 8 , значит решений в целых числах нет.

Ответ: нет

Нелинейные диофантовы уравнения с помощью учета свойств делимости и остатков

Пример 11. (Третий этап олимпиады, 2011г, 11 класс)

Существуют ли такие целые числа х и у, что

Решение. 1) При делении на 9 куб числа дает остатки 0,1 или 8,

т. е.

2) Значит,

3) Тогда

4) Но 2011

Ответ: нет

0,то 4) Но 2400 не делится на 9. Значит, при у0 целых решений нет 3) Тогда   5) Тогда у=0, значит, х=7 или х=-7. Ответ: (7;0), (-7;0) " width="640"

Нелинейные диофантовы уравнения с помощью учета свойств делимости и остатков

Пример 12. (Третий этап олимпиады, 2014г, 9класс)

Найти все пары х и у, которые удовлетворяют равенству

Решение. 1) Если у

2)

Если у0,то

4) Но 2400 не делится на 9. Значит, при у0 целых решений нет

3) Тогда

5) Тогда у=0, значит, х=7 или х=-7.

Ответ: (7;0), (-7;0)

Нелинейные диофантовы уравнения методом ограниченного перебора

Пример 13. (Заключительный этап олимпиады , 2015г, 8 класс)

Найти все пары натуральных чисел (n;m), для которых верно равенство

Решение. Заметим, что при , выражение оканчивается на два нуля. Тогда оканчивается на 05. Но квадрат числа не может оканчиваться на 05. Поэтому для чисел больше 9 решений нет.

Проверив для значения от 1 до 9 найдем решения.

Ответ: (4;23),(5;25),(6;35).

Нелинейные диофантовы уравнения с помощью комбинации методов

Пример 14. (Заключительный этап олимпиады,2014г, 10 класс)

Найти целые решения уравнения

Решение.

• Р

Получаем первую серию решений a=b=t,

2) Решение уравнения как квадратного относительно переменной a

Решив полученное неравенство методом интервалов, получим

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

Ответ: (-18;-2), (0;7),(12;3), a=b=t,

Нелинейные диофантовы уравнения другие методы

Существуют и другие методы решения диофантовых уравнений. Например,

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

Спасибо за внимание!