Методы решения диофантовых уравнений.

Слайд #1

Методы решения диофантовых уравнений

Слайд #2

Понятие диофантовых уравнений. Теоремы.
С уравнениями в математике (да и в повседневной жизни) нам приходится сталкиваться постоянно. В школьном курсе математики рассматриваются далеко не все из огромного множества уравнений.
Немного подзабытыми и недостаточно изученными являются диофантовы (неопределенные) уравнения. Скорее всего, каждому из нас приходилось не один раз решать уравнения в целых числах, возможно , даже не задумываясь над этим.

Слайд #3

Задача №1.
Вы должны уплатить за купленный в магазине свитер 19 рублей. У вас одни лишь трехрублевки, у кассира - только пятирублевки. Можете ли вы при наличии таких денег расплатиться с кассиром и как именно?
Комментарий к задаче:
Вопрос задачи сводится к тому, что бы узнать сколько вы должны бать кассиру трехрублевок, что бы получить сдачу пятирублевками, уплатить 19 рублей. Неизвестных в задаче две – число трехрублевок, пусть будет Х, а число пятирублевок, пусть будет У. Но составить мы можем лишь одно уравнение: 3Х-5У=19.
Хотя одно уравнение с двумя неизвестными имеет бесконечное множество решений, но еще не очевидно, что среди них найдется хоть одно с целыми положительными значениями Х и У. Вот мы и пришли к задаче, решаемой диофантовым уравнением.

Слайд #4

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

Общий вид диофантового уравнения с двумя неизвестными: aX+bY=c. Например, 5Х+8У=39, Х 2 −3 У 2 =1.

Слайд #5

Задача №2.
Определите, является ли диофантовым уравнение. Аргументировать свой ответ.
а) 71х-9у=1
б) 5х+8у=2,6
в) х 2 + у 2 =9
г) 5,1х+4,6 у 2 =8
д) 6y+13x-2z=8
e) -9x+17z=0
Примечание: диофантовы уравнения имеют целые коэффициенты.

Слайд #6

Термин диофантовы уравнения берет свое начало от имени выдающегося греческого ученого математика Диофанта из Александрии. К сожалению, мы до сих пор не знаем точно, в каком веке он жил, однако большинство историков математики относят его работы к III веку. О его жизни нам практически ничего не известно, из исключением нескольких незначительных фактов, которые упоминаются в одной стихотворной задаче, вошедшей в более поздний греческий сборник математических головоломок.
Если в этой задаче приведены действительные факты, то, значит, Диофант женился в 33 года, у него был сын, умерший в среднем возрасте, а сам Диофант дожил до 84 лет.

Слайд #7

До нашего времени дошла примерно половина (6 из 13 книг) его главного труда – математического трактата «Арифметика» (250-275гг.). В нем подается 189 задач с решениями и пояснениями. По форме «Арифметика» просто сборник задач, но по содержанию - уникальное явление, настоящее чудо в истории математики. Уже вступление к этой книге свидетельствует о великом шаге вперед, который сделал Диофант в сравнении с математиками классической древности. Для обозначения неизвестного и его степеней, знака равенства Диофант употреблял сокращенную запись слов. Он искусно решал алгебраические и теоретико-числовые задачи, не давая общих методов решения. Диофант строил алгебру на арифметике, при этом со своим языком и символикой. Его можно считать автором первого алгебраического языка.
Поскольку большинство задач в этой книге предусматривает решения в целых числах, то для анализа подобного рода проблем стал применяться термин диофантов.
Сегодня диофантов анализ – это обширная, сложная область теории чисел, которой посвящена многотомная научная литература.

Слайд #8

Теперь выясним всегда ли возможно решить неопределенное уравнение в целых числах. Ответом на этот вопрос служат две теоремы:
Теорема 1: Если свободный член неопределенного уравнения aх+by=с не делится на наибольший общий делитель коэффициентов a и b, то уравнение не имеет целых решений. (Утверждает, что условие НОД(a;b)=1 является необходимым условием для разрешимости неопределенного уравнения ax+by=c в целых числах.)
Теорема 2: Если коэффициенты a и b неопределенного уравнения ax+by=c являются взаимно простыми числами, то уравнение имеет, по крайней мере, одно целое решение. (Утверждает, что это условие является достаточными.)

Слайд #9

Задача №3.
Используя вышеприведенные теоремы определите, имеют ли решения следующие диофантовы уравнения:
А) 6х+12у=13
Б) 6х+7у=14
В) 18х+9z=82
Г) 7х+4у=56
Д) х+2у=1

Слайд #10

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

Слайд #11

Решим уравнение первой ступени.
Задача №4
Вы должны за купленный в магазине свитер 19 рублей. У вас одни лишь трехрублевки, у кассира только пятирублевки. Можете ли вы при наличии таких денег расплатиться за свитер и как и как именно?
Решение:
Выразим х через у: х= 19+5у 3 =6+у+ 1+2у 3 .
Так как х,у,6 – целые числа, равенство будет верным если 1+2у 3 так же целое число. Обозначим это выражение буквой t . Тогда х=6+у+t, где t= 1+2𝑦 3 , значит 3t=1+2y, а 2y=3y-1.
Поэтому у= 3𝑡−1 2 =𝑡+ 𝑡−1 2 .

Слайд #12

Так как y, t – целые числа, то и 𝑡−1 2 должно быть целым числом 𝑡 2 . Тогда 𝑦=𝑡+ 𝑡 2 , где 𝑡 2 = 𝑡−1 2 , значит 2𝑡 2 =𝑡−1и 𝑡= 2𝑡 2 +𝑡.
Значение t=2 𝑡 2 +𝑡 подставляем в предыдущие равенства:
𝑦=𝑡+𝑡 2 = 𝑡 2 +1 +𝑡
𝑥=6+𝑦+𝑡=6+ 3𝑡 2 +1 + 2𝑡 1 +1 =𝑠+5 𝑡 2
Итак мы нашли выражения для х и у. Мы знаем, что эти числа не только целые, но и положительные:
𝑠+ 𝑡 2 >0 и 3 𝑡 2 +1>0.
Решив неравенства, заключаем, что 𝑡 2 =0, 1, 2, 3, …
Соответствующие значения х=8, 13, 18, 23, а у=1, 4, 7,10, …
Уравнение решено.

Слайд #13

Задание №5
Самостоятельно закончите решение задачи, интерпретировав ответ:
Решая задачу мы получили следующие формулы для переменных 𝑦=3 𝑡 2 +1 и 𝑥=8+5 𝑡 2 , который как оказывается связаны с коэффициентами исходного уравнения.
Теорема 3 : Диофантовы уравнения вида ax+by=c, где a,b,c- целые числа, а также a и b – взаимно простые числа, имеет следующий ряд решений : если х 0 и у 0 - одно решение, то числа х= х 0 +𝑏𝑛, 𝑦= 𝑦 0 −𝑎𝑛
(n- любое число) тоже будет решениями.

Слайд #14

Доказательство:
Подставим в данное диофантово уравнение значение х и у. Получим
𝑎 𝑥 0 +𝑏𝑛 +𝑏 𝑦 0 −𝑎𝑛 =𝑐.
Раскроем скобки и приведем подобные
𝑎 𝑥 0 +𝑎𝑏𝑛+𝑏 𝑦 0 −𝑏𝑎𝑛=𝑐
𝑎 𝑥 0 +𝑏 𝑦 0 =𝑐
Что и требовалось доказать.

Слайд #15

Таким образом, используя формулы и рассуждения можно без особых усилий решать неопределенные уравнения первой степени с небольшими коэффициентами.
Задание № 6.
Самостоятельно найдите не менее четырех целых решений уравнений.
А) 5х+8у=39
Б) 8х-5у=19
В) 7х-5у=1
Г) 32х+20у=1076
Примечание: первое решение уравнений попытайтесь подобрать устно, а следующие найдите по формулам.

Слайд #16

Метод спуска бесспорно удобен и наиболее прост для решения уравнений вида ax+by=c. Однако часто встречаются диофантовы уравнения, которые не относятся к приведенному выше типу. Эти уравнения, как правило, можно решить только путем использования специфических приемов и методов.
Сначала остановимся на тех случаях, когда левая часть уравнения путем тождественных преобразований целесообразно разложить на множители и привести решение неопределенного уравнения с двумя неизвестными к решению эквивалентной совокупности систем уравнений.
Рассмотрим этот метод, найдя все целые числа, которые являются решениями уравнения ху-3х+5у=25

Слайд #17

Решение:
Необходимо путем тождественных преобразований в левой части получить два множителя:
Ху-3х+5у=25
Х(у-3)+5у=25
Х(у-3)+6у-15=10
Х(у-3)+5(у-3)=10
(у-3)(х-5)=10
Из последнего уравнения получаем, что числа (у-3) и (х+5) являются делителями числа 10.

Слайд #18

Число 10 имеет 8 делителей: ±1, ±2, ±5, ±10.
Отсюда следует, что мы получаем 8 систем уравнений:
х+5=1 у−3=10
х+5=−1 у−3=−10
и так далее.

Слайд #19

Рассмотрим еще один пример.
Найдите все целые решения уравнения х 2 − 4у 2 =13
Решение:
х 2 − 4у 2 =13
х−2у х+2у =13
Делители 13: ±1; ±13.
Поэтому уравнение будет эквивалентно совокупности следующих систем:
х−2у=1 х+2у=13 ; х−2у=13 х+2у=1 ; х−2у=−1 х+2у=−13 ; х−2у=−13 х+2у=−1 .
Решением уравнения будут следующие пары целых чисел: (7;3), (7;-3), (-7;-3), (-7;3).

Слайд #20

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


Пример: решим уравнение в целых числах 3 х 2 +ху+ у 2 =х+8у

Слайд #21

Решение:
Рассмотрим уравнение, как квадратное относительно х:
3 х 2 +3ху+3 у 2 −х−8у=0
3 х 2 +3ху−х+3 у 2 −8у=0
3 х 2 + 3у−1 х+3 у 2 −8у=0
D= (3у−1) 2 −4∗3∗ 3у 2 −8у = 9у 2 −6у+1−36 у 2 +96у=−27 у 2 +90у+1
Данное уравнение имеет корни, если дискриминант больше 0:
−27 у 2 +90у+1≥0
27 у 2 −90у−1≤0
𝐷 4 = 45 2 +27=2052

Слайд #22

у 1 = 45+ 2052 27 ; у 2 = 45− 2052 27
Итак, у находится в отрезке [ 45− 2052 27 ; 45+ 2052 27 ]
Так как значение у только целые, то удовлетворяет условию числа:
0; 1; 2; 3.
Перебирая значения получим две пары ответов: (0;0) и (1;1).

Слайд #23

Задание № 7.
Самостоятельно найдите все решения уравнений в множестве целых чисел.
А) ху+3х-5у=-3
Б) х 2 −9 у 2 =19
В) х 3 + у 3 =35

Примечание: используйте формулы сокращенного умножения.