Диафантовые уравнения

Оглавление
1. Введение
2. История возникновения диофантовых уравнений
3. Общее решение линейных диофантовых уравнений
3.1 Однородные уравнения
3.2 Общие линейные уравнения
4. Примеры задач
Задача 1
Задача 2 (одна из задач Диофанта)
Задача 3
Задача 4
5. Заключение
Список использованных источников
Приложение 1

Диафантовые уравнения

По этой причине 10-ую проблему Гильберта можно рассматривать не только как математическую проблему, но и проблему теоретической информатики, которая в 1900 году еще не существовала как самостоятельная дисциплина. Гипотезу, что такого способа нет, первым выдвинул американский математик М. Дэвис в 1949 г. В 1970 г. ленинградский математик Юрий Владимирович Матиясевич доказал, что такого общего метода не существует.Сегодня мы знаем, что 10-ая проблема Гильберта неразрешима - требуемого в ней алгоритма не существует. Однако в 1900 году это утверждение нельзя было даже сформулировать строго математически.Однако если про произвольное диофантово уравнения нельзя сказать, имеет ли оно целые корни, или нет, то проблема существования целых корней линейных уравнений решена.3. Общее решение линейныхдиофантовых уравнений Приведем здесь формулировки теорем, на основании которых может быть составлен алгоритм решения неопределенных уравнений первой степени с двумя переменными в целых числах.3.1 Однородные уравненияПрежде всего, мы рассмотрим однородные линейные уравнения, т.е. уравнения вида ах + by = 0. Справедлива следующая теорема, которая дает полное решение диофантовых уравнений вида ах + by = 0. Теорема 1. Если ax=by (a, b, x, y∈Z) и НОД(a, b)=1, то x, y можно представить в виде x=bt, y=at, где t — некоторое целое число.Доказательство. Рассмотрим два случая:1) b≠0. По условию (ax) ⋮ b, НОД(a, b)=1; следовательно, x ⋮ b, т. е. x=bt, где t∈Z. Тогда y= axb= abt b=at.2) b=0. Тогда a≠0, и исходное уравнение принимает вид ax=0, откуда x=0. Поскольку НОД(a,b)=1, то a=±1. Тогда, полагая t= ya, имеем: y=аt, x=0=0·t=bt (число t является целым, поскольку a=±1).Замечание. Если НОД (а,b)=d, то обе части уравнения ах + by = 0 можно поделить на d. Поэтому, не нарушая общности, можно считать, что числа а и b – взаимно простые.Пример 1. Решить в целых числах уравнение 80х + 126y = 0.Решение. Перейдем от данного уравнения к равносильному: 40х= – 63у. Поскольку НОД (40, 63)=1, то по теореме 1все целочисленные решения этого уравнения имеет вид х = – 63t, у=40t, где t ∈ Z.Ответ: х = – 63t, у=40t, где t ∈ Z.3.2 Общие линейные уравнения Простейшим диофантовым уравнением является уравнение ах + by = с, где a, b, с ∈ Z и хотя бы один из коэффициентов a и b не равен нулю.Как по коэффициентам диофантова уравнения определить, имеет ли оно целочисленные решения? И если имеет, то, как найти все эти решения? Ответы на эти вопросы дают приведенные ниже теоремы.Теорема 2. Уравнение ах + by = с (*), где a, b, с ∈ Z и хотя бы один из коэффициентов a и b не равен нулю, имеет решения в целых числах тогда и только тогда, когда c⋮НОД(a, b).Доказательство. Пусть данное уравнение имеет решения в целых числах, и пусть (x0, y0) – произвольное целочисленное решение этого уравнения. Тогда ax0+by0=c. По определению a⋮НОД(a,b) и b⋮НОД(a,b); тогда и (ax0) ⋮НОД(a,b), (by0) ⋮НОД(a,b). Следовательно, и c=(ax0+by0)⋮НОД(a,b), что и требовалось доказать.Пример 2. Имеют ли данные уравнения решения в целых числах:а) 6х – 16у=220; б) 105х+42у=56?Решение. а) НОД (6,16)=2 и 220⋮2, поэтому данное уравнение имеет целочисленные решения.б) НОД (105,42)=21, 56 не делится на 21, значит, целочисленных решений нет.Ответ: а) да; б) нет.Теорема 3. Если НОД(a, b)=1 и (x0, y0) − некоторое целочисленное решение уравнения (*), то все решения этого уравнения в целых числах имеют вид x=x0−bt, y=y0+at, где t∈Z.Замечание. Необходимо доказать два утверждения:1) если (x1, y1) − некоторое целочисленное решение уравнения (*), то x1, y1 представляются в виде x1=x0−bt, y1=y0+at, где t∈Z;2) для любого t∈Z пара (x0−bt, y0+at) является решением уравнения (*).Доказательство. 1) Поскольку пары (x0, y0) и (x1, y1) являются решениями уравнения ax+by=c, то ax0+by0=c и ax1+by1=c, откуда ax0+by0=ax1+by1, или a(x0 –x1)=b(y1–y0). По условию НОД(a, b)=1, тогда x0–x1=bt, y1–y0=at, где t – некоторое целое число; значит, x1=x0−bt, y1=y0+at.2) Подставив пару (x0−bt, y0+at) в уравнение (*), получим: a(x0−bt)+b(y0+at)= =ax0−abt+by0+abt=ax0+by0=c. Следовательно, эта пара является решением уравнения (*). Теорема доказана [3].Сформулированные теоремы позволяют составить следующий алгоритм решения в целых числах уравнения вида ax+by=c, где а, b, с ∈ Z.1. Вычислить НОД (а, b); если НОД (а, b)=d >1и с не делится на d, то уравнение целых решений не имеет. НОД (а, b) может быть найден с помощью алгоритма Евклида.2. Если НОД (а, b)=d >1 и с делится на d, то разделить обе части уравнения ax+by=c на d, получив уравнение, в котором коэффициенты будут взаимно просты.3. Найти (х0, у0) – частное решение, например, методом перебора.4. Составить общую формулу целых решений данного уравнения х=х0c+bt, y=y0с – аt, где х0, у0 – целое решение уравнения ах+bу=1, t ∈ Z.4. Примеры задачЗадача 1На складе имеются гвозди в ящиках по 16, 17 и 40 кг. Может ли кладовщик выдать 100 кг гвоздей, не вскрывая ящика?Решение.Пусть 1 ящик по 40 кг. Комбинируем другие ящики. Пусть 1 ящик по 17 кг, тогда останется 43. Взять по 16 кг невозможно.Пусть 2 ящика по 17 кг, тогда останется 26 кг. Целых ящиков по 16 кг не получится.Пусть 3 ящика по 17 кг, тогда останется 9 кг, которые придется выдавать, вскрыв какой-нибудь ящик.Значит, ящики по 40 кг нам не нужны. Значит, получается уравнение:16 х + 17 у = 100.Перебирая варианты с 16 кг и 17 кг ящиками, получим единственное решение: 4 ящика по 17 кг и 2 ящика по 16 кг.