Главная / Математика / Исследовательская работа "Диофантовы уравнения"

Исследовательская работа "Диофантовы уравнения"


Оглавление




Введение.

Определение 1. Диофантовым уравнением 1-ой степени (линейным) с hello_html_m601acf03.gif неизвестными называется уравнение вида

hello_html_m4f4a59de.gif,

где все коэффициенты и неизвестные – целые числа и хотя бы одно hello_html_m7f8a2d6c.gif.

Для сокращения записи условимся далее сокращать фразу линейное диофантово уравнение, как ЛДУ.

Определение 2. Решением ЛДУ называется упорядоченная n-ка целых чисел hello_html_38661a9a.gif, такая, что hello_html_m7ed29581.gif.

1. Диофант и история диофантовых уравнений.


Диофант (Dióphantos) представляет одну из занимательных загадок в истории математики. Никто не знает, кем был Диофант, точные года его жизни, не известны его предшественники, которые работали бы в той же области, что и он. [10]

На могиле Диофанта есть стихотворение-загадка, решая которую нетрудно подсчитать, что Диофант прожил 84 года. О времени жизни Диофанта можно судить по работам французского исследователя науки Поля Таннри - это, приблизительно, середина III в.н.э. [10]

Наиболее интересным представляется творчество Диофанта. «Труды его подобны сверкающему огню среди полной непроницаемой тьмы». [Стройк] До нас дошло 7 книг из, возможно, 13 [1], которые были объединены в «Арифметику». Стиль и содержание этих книг резко отличаются от классических античных сочинений по теории чисел и алгебре, образцы которых известны по «Началам» Евклида, леммам из сочинений Архимеда и Аполлония. «Арифметика», несомненно, явилась результатом многочисленных исследований, многие из которых остались неизвестными.

«Арифметика» Диофанта – это сборник задач (их всего 189), каждая из которых снабжена решением и необходимым пояснением. В собрание входят весьма разнообразные задачи, а их решение часто в высшей степени остроумно. Диофант практиковался в нахождении решений неопределенных уравнений вида hello_html_m5395edc8.gif, hello_html_m34986bae.gif или систем таких уравнений. Типично для Диофанта, что его интересуют только положительные целые и рациональные решения. Иррациональные решения он называет «невозможными» и тщательно подбирает коэффициенты так, чтобы получились искомые положительные, рациональные решения.

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

Неопределенные уравнения 1-й степени начали рассматриваться индусскими математиками позднее, примерно с V века. Некоторые такие уравнения с двумя и тремя неизвестными появились в связи с проблемами, возникшими в астрономии, например, при рассмотрении вопросов, связанных с определением периодического повторения небесных явлений.[2]

Первое общее решение уравнения первой степени hello_html_m1dc65202.gif, где hello_html_m65b62c8c.gif - целые числа, встречается у индийского мудреца Брахмагупты (ок. 625 г). Поэтому, строго говоря, нет оснований называть линейные неопределенные уравнения диофантовыми. Однако исторически все же сложилось применять термин «диофантово», к любому уравнению, решаемому в целых числах.

В 1624 г. в публикуется книга французского математика Баше де Мезирьяка «Problẻmes plaisans et delectables que se font par les nombres». Баше де Мезирьяк для решения уравнения hello_html_m1dc65202.gif фактически применяет процесс, сводящийся к последовательному вычислению неполных частных и рассмотрению подходящих дробей.

После Баше де Мезирьяка в XVII и XVIII веках различные правила для решения неопределенного уравнения 1-й степени с двумя неизвестными давали Роль, Эйлер, Саундерсон и другие математики.

Цепные дроби к решению таких уравнений были применены Лагранжем, который, однако, замечает, что фактически это тот же способ, который был дан Баше де Мезирьяком и другими математиками, рассматривавшими неопределенные уравнения до него. Неопределенные уравнения 1-й степени стали записываться и решаться в форме сравнения значительно позже, начиная с Гаусса. [2]

В августе 1900 г. в Париже состоялся II Международный конгресс математиков. 8 августа Д.Гильберт прочитал на нем доклад "Математические проблемы". Среди 23 проблем, решение которых (по мнению Д.Гильберта) совершенно необходимо было получить в наступающем XX в., десятую проблему он определил следующим образом:

"Пусть задано диофантово уравнение с произвольным числом неизвестных и рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых числах". [7]

Гипотезу, что такого способа нет, первым выдвинул (с достаточным на то основанием) американский математик М.Дэвис в 1949 г. Доказательство этой гипотезы растянулось на 20 лет - последний шаг был сделан только в 1970 г. Юрием Владимировичем Матиясеевичем, на первом году аспирантуры он показал алгоритмическую неразрешимость 10 проблемы Гильберта.

Однако если про произвольное диофантово уравнения нельзя сказать, имеет ли оно целые корни, или нет, то проблема существования целых корней ЛДУ решена.

2. Число решений ЛДУ.


Теорема 1. При взаимно простых коэффициентах hello_html_65a09b19.gif диофантово уравнение

hello_html_12df94e9.gif

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

Доказательство. Обозначим через hello_html_465b1232.gifмножество тех положительных чисел hello_html_559071c1.gif, для которых уравнение

hello_html_m4f4a59de.gif

имеет решение в целых числах. hello_html_465b1232.gif, очевидно, не пусто, так как при заданных hello_html_65a09b19.gif, можно подобрать целые значения hello_html_120f6006.gif, такие, чтобы hello_html_320a8c13.gif было положительным числом.

В множестве hello_html_465b1232.gifсуществует наименьшее число (hello_html_465b1232.gif – подмножество натуральных чисел), которое мы обозначим через hello_html_m3eb4d443.gif hello_html_51af425e.gif Обозначим через hello_html_mc853465.gif - целые числа, такие, что

hello_html_m2bd9dc06.gif.

Пусть hello_html_68de213e.gif, где hello_html_6202382f.gif; тогда

hello_html_5da7b45e.gif

hello_html_314131f9.gif.

Мы подобрали целые значения: hello_html_m24fb5b14.gif, hello_html_7995b07b.gif,…, hello_html_m6a95766a.gif, такие, что hello_html_7501fd42.gif, но hello_html_6202382f.gif, а hello_html_m3eb4d443.gif - наименьшее положительное число в hello_html_465b1232.gif, т. е. hello_html_m4df10123.gif не может быть положительным, hello_html_m5b00bd2f.gif, hello_html_52109efc.gif, hello_html_57cb3dd5.gif.

Аналогично получаем: hello_html_m497ed1c8.gif,…,hello_html_m3769a36c.gif.

Мы видим, что hello_html_m3eb4d443.gif – общий делитель чисел hello_html_65a09b19.gif, следовательно, поскольку hello_html_m24bf6ec.gif, hello_html_m50caf123.gif, hello_html_3356b487.gif, hello_html_m159b6f2b.gif, то уравнение разрешимо в целых числах.


Теорема 2. Пусть hello_html_m3eb4d443.gif - наибольший общий делитель коэффициентов hello_html_65a09b19.gif. Диофантово уравнение имеет решение тогда и только тогда, когда hello_html_1c32fc3b.gif. Число решений такого уравнения равно либо нулю, либо бесконечности.

Докажем последовательно все три утверждения теоремы.

1). Пусть hello_html_1c32fc3b.gif. Для уравнения

hello_html_1ad59380.gif,

где hello_html_1483272f.gif, существуют целые числа: hello_html_2d3e94ec.gif удовлетворяющие ему. Т.е. такие, что

hello_html_bd3e966.gif.

Тогда

hello_html_m554ff073.gif

т. е. hello_html_14569d5e.gif - решение уравнения.

2). Пусть теперь hello_html_m3eb4d443.gif не делит hello_html_559071c1.gif. Тогда левая часть уравнения при любых целых hello_html_120f6006.gif делится на hello_html_m3eb4d443.gif, а правая на hello_html_m3eb4d443.gif не делиться, так что равенство при целых значениях hello_html_120f6006.gif невозможно.


3). Если hello_html_38661a9a.gif - упорядоченная n-ка чисел, удовлетворяющий уравнению, то например, все n-ки

hello_html_3fbe080a.gifпри hello_html_m2a090d69.gif

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

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


3. Нахождение решений для некоторых частных случаев ЛДУ.

3.1. ЛДУ c одной неизвестной.

Рассмотрим линейное уравнение с одной неизвестной, т.е. уравнение вида

hello_html_3fc26f61.gifhello_html_m1ce2dbb.gif

Ясно, что решением данного уравнения будет hello_html_m4378d531.gif, и решение будет целым числом только в том случае, когда hello_html_55a8a6db.gif.


3.2. ЛДУ с двумя неизвестными.

Рассмотрим линейное уравнение с двумя неизвестными:

hello_html_1449dc3f.gif, hello_html_19550414.gif.

Существует несколько алгоритмов для нахождения решения.

Способ 1.

Пусть hello_html_m969438a.gif

Рассмотрим два случая:

а) hello_html_m12550da.gif не делится на hello_html_m3eb4d443.gif. В этом случае решений нет по теореме 2.

б) hello_html_m12550da.gif делится на hello_html_m3eb4d443.gif, поделим на hello_html_m3eb4d443.gif.

hello_html_19a4123e.gif;

hello_html_4db941bc.gif.

Таким образом получили новое ЛДУ, с тем же множеством решений, но уже со взаимно-простыми коэффициентами. Поэтому далее мы будем рассматривать именно такие уравнения.

Рассмотрим hello_html_1449dc3f.gif, hello_html_m3d006e08.gif.

hello_html_m27e2c09.gif, перейдем к сравнению,

hello_html_407826f6.gif.

Т.к. hello_html_m3d006e08.gif, то сравнение имеет единственное решение hello_html_m510ebadb.gif.

hello_html_m2bac419c.gif; подставим в уравнение.

hello_html_m8678bd9.gif;

hello_html_m21dc5f19.gif;

hello_html_m77b5ab7b.gif, причем hello_html_5b9a2a0.gif.

Обозначим hello_html_m3edb88f1.gif.

Тогда общее решение можно найти по формулам: hello_html_m15264d7.gif, где hello_html_7f0652f6.gif.

Пример. hello_html_m4061548c.gif, hello_html_21ad91bb.gif.

Найдем решение сравнения hello_html_1a3fdfb1.gif;

hello_html_54d0b86c.gif;

hello_html_7eec9815.gif, т.е. hello_html_m437c872e.gif

hello_html_7353ee20.gifhello_html_7e8ed3d2.gif.

hello_html_3c51ca3e.gif;

hello_html_m6cc78997.gif

Получили общее решение: hello_html_1a6a473d.gif, где hello_html_7f0652f6.gif.

Способ 2.

Рассмотрим еще один способ нахождения решения ЛДУ с двумя неизвестными, а для этого рассмотрим уравнение вида hello_html_628da9fd.gif. Уравнения такого вида называются линейными однородными диофантовыми уравнениями (ЛОДУ). Выражая неизвестную hello_html_m5547f17b.gif, через неизвестную hello_html_m11fb3721.gif приходим к hello_html_54eb7a4a.gif. Так как x должен быть целым числом, тоhello_html_m225d6514.gif, где hello_html_25ca66e5.gif- произвольное целое число. Значитhello_html_9b47c79.gif. Решениями ЛОДУ hello_html_628da9fd.gif являются n-ки вида hello_html_m4e76f3d2.gif, где hello_html_7f0652f6.gif. Множество всех таких n-ок называется общим решением ЛОДУ, любая же конкретная пара из этого множества называется частным решением.

Рассмотрим уравнение hello_html_1449dc3f.gif, hello_html_m3d006e08.gif. Пусть n-каhello_html_m55f9e8e0.gif его частное решение, а множество n-ок hello_html_m4e76f3d2.gif общее решение соответствующего ЛОДУ. Докажем предложение.

Общее решение ЛДУ hello_html_1449dc3f.gif, hello_html_m3d006e08.gif задается уравнениями hello_html_m15264d7.gif, где hello_html_7f0652f6.gif.

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения hello_html_1449dc3f.gif имеет именно такой вид, какой указан в формулировке предложения. Пусть hello_html_2f78b293.gif- какое-нибудь решение уравнения hello_html_1449dc3f.gif. Тогда hello_html_m5371a3fa.gif, но ведь и hello_html_3cb78972.gif. Вычтем из первого равенства второе и получим:

hello_html_m64317330.gif- однородное уравнение. Пишем сразу общее решение: hello_html_58b3e5d5.gifhello_html_m6d9e224f.gif, откуда получаем:

hello_html_6a044238.gif. Доказательство завершено.

Рассмотрим частное решение ЛДУ.

hello_html_m3d006e08.gif

По теореме о линейном разложении НОД, это означает, что найдутся такие hello_html_mcbbf10b.gif и hello_html_397c1811.gif из множества целых чисел, что hello_html_129ae830.gif, причем эти hello_html_mcbbf10b.gif и hello_html_397c1811.gif легко можно найти с помощью алгоритма Евклида. Умножим теперь равенство hello_html_129ae830.gif на hello_html_m12550da.gif и получим: hello_html_m18bd72b1.gif, т.е.hello_html_m2ef00ed2.gif, hello_html_44be0c3d.gif.

Таким образом, для нахождения общего решения находим общее решение ЛОДУ, частное решение ЛДУ и их складываем.

Замечание: особенно этот способ удобен, когда hello_html_m4d99304b.gif или hello_html_m32e2186b.gif. Если, например, hello_html_m4d99304b.gif, hello_html_9cde818.gif, тогда n-ка hello_html_4c51cc6d.gif, очевидно, будет частным решением ЛДУ. Можно сразу выписывать общее решение.


Пример. hello_html_m4061548c.gif, hello_html_21ad91bb.gif.

Найдем частное решение. Используем алгоритм Евклида.

hello_html_m6928ad6e.gif;

hello_html_m50172c7c.gif

Получаем линейное разложение НОД:

hello_html_406199a5.gif, т.е hello_html_66f5bafb.gif.

hello_html_m2712fb01.gif, hello_html_7c9c26d3.gif

Получили общее решение: hello_html_59073681.gif, где hello_html_m179fc20.gif.

Таким образом получили решение, не совпадающее с решением, найденным первым способом.

Обозначим hello_html_m42764e6f.gif и получим hello_html_1a6a473d.gif, т.е эти решения равносильны.

Способ 3.

Еще один способ опирается на теорему:

Пусть hello_html_m55f9e8e0.gif - произвольное решение диофантова уравнения

hello_html_1449dc3f.gif, hello_html_m3d006e08.gif, тогда

множество решений уравнения в целых числах совпадает с множеством пар hello_html_487eb9a0.gif, где hello_html_55ca9365.gif, hello_html_m1ba01617.gif, где t – любое целое число.

Доказательство этого несложного факта можно найти в книге Бухштаба [2, стр. 114].

Частное решение можно легко отыскать с помощью алгоритма Евклида.

4. Нахождение решений произвольного ЛДУ.


Перейдем теперь к решению ЛДУ с hello_html_m601acf03.gif неизвестных, т. е. уравнений вида

hello_html_m4f4a59de.gif

где все коэффициенты и неизвестные – целые числа и хотя бы одно hello_html_m7f8a2d6c.gif. Для существования решения по теореме 2, необходимо, чтобыhello_html_1ec68f24.gif

Положив

hello_html_m6ae22976.png

перейдем к равносильному уравнению

hello_html_m4a6483a5.gif(*),

гдеhello_html_m53d4ecad.gifhello_html_m23874ae.gif. Пустьhello_html_2d912e3c.gif,  hello_html_14517672.gif - два ненулевых числа, таких, что hello_html_da257a9.gif Для определенности предположим, чтоhello_html_45f1ac11.gif, hello_html_m456c6106.gif Разделив с остатком hello_html_2d912e3c.gif на hello_html_14517672.gif, получим представление hello_html_50fb800.gif. Заменив hello_html_2d912e3c.gif на hello_html_44dfa419.gif в уравнении (*), приведем его к виду

hello_html_m5ed525ff.gif

Перепишем это уравнение в виде

hello_html_1e458ca.gif(**)

где

hello_html_m29f4cf40.gif, hello_html_m670281e3.gif.

Очевидно, что решения уравнения (*) и (**) связаны между собой взаимно однозначным соответствием и, таким образом, решив уравнение (**), несложно найти все решения уравнения (*). С другой стороны отметим, что

hello_html_313e4103.gifhello_html_230800f6.gif

Отметим также, что

hello_html_6debe1ab.gif

Следовательно, за конечное число шагов уравнение (*) приведется к виду

hello_html_mc8c5778.gif(***)

где числа hello_html_m1e09ca3f.gif  (i = 1,...,n), которые не равны нулю, равны между собой по абсолютной величине. Из соотношения hello_html_4db2be70.gif следует, что числа hello_html_m1e09ca3f.gif могут принимать только значения 0,±1, причем не все из них равны нулю. Предположим, для определенности, hello_html_mea912a4.gif. Тогда уравнение (***) имеет следующее решение:

hello_html_69c2c119.gif

где t2, t3, ..., tn - произвольные целые числа. Отсюда, учитывая проведенные замены, получается и решение уравнения (*). Отметим, что при получении решения уравнения (***) использовался лишь факт, что hello_html_d0e432f.png, поэтому, при выполнении алгоритма можно остановиться на том шаге, когда хотя бы один из коэффициентов станет равным ±1.

5. Пример решения ЛДУ на Turbo Pascale.

5.1 Алгоритм решения.

a1x1 + a2x2 + ... + anxn = НОД(a1, a2, ..., an ).

Функция NOD(n, a(), x())

Задать набор Nai {1,0,...,0}

Цикл i от 2 до n

Задать набор Nai {0,0,...,0,1i,0,...,0}

Пока a(i) ≠ 0

q = a(1)/a(i)

t = a(i); Nt = Nai {набор временный}

a(i) = a(1) - q*a(i);

Nai = Na1 - q*Nai {покомпонентно}

a(1) = t Na1 = Nt

Конец пока

{набор Nai содержит решение} {однородного уравнения}

Конец цикла i

NOD = a(1) {НОД коэффициентов}

x() = Na1

{набор Na1 содержит частное решение} {уравнения}

конец функции

5.2 Листинг программы на Turbo Pascale.

type

TVector = array [1..100] of Integer;

var

n, i, a1, ai, tmp: Integer;

a, x1, xi: TVector;

procedure SetUnitVector (var v: TVector; index: Integer);

begin

FillChar (v, Size Of (TVector), 0);

v[index] := 1;

end;


procedure Calculate Vector (var v1, v2:TVector; q: Integer);

var

i, tmp: Integer;

begin

for i := 1 to n do

begin

tmp := v2[i];

v2[i] := v1[i] - q * v2[i];

v1[i] := tmp;

end;

end;


begin

Write ('Введите количество компонент n: ');

Readln (n);

Write('Введите компоненты Ai через пробел: ');

for i := 1 to n do Read(a[i]);

Readln;


Set Unit Vector (x1, 1);

a1 := a[1];

for i := 2 to n do

begin

SetUnitVector (xi, i);

ai := a[i];

while ai <> 0 do

begin

Calculate Vector (x1, xi, a1 div ai);

tmp := ai;

ai := a1 mod ai;

a1 := tmp;

end;

end;


Writeln ('HОД = ', a1);

for i := 1 to n do Write(x1[i], ' ');

Writeln;

end.


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

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

4x - 6y + 11z = 7, (4,6,11)=7

Разделив с остатком -6 на 4, получим -6 = 4(-2) + 2. Представим исходное уравнение в виде

4(x - 2y) + 2y + 11z = 7.

После замены x = x - 2y это уравнение запишется следующим образом

4x + 2y + 11z = 7.

Учитывая, что 11 = 2·5 + 1, преобразуем последнее уравнение:

4x + 2(y + 5z) + z = 7.

Положив y = y + 5z, получим

4x + 2y + z = 7.

Это уравнение имеет следующее решение: x, y - произвольные целые числа, z = 7 - 4x - 2y.

Следовательно y = y - 5z = 20x + 11y - 35, x = x + 2y = 41x + 22y - 70.

Таким образом, решение исходного уравнения имеет вид

hello_html_10999d63.gif, гдеhello_html_108e64f7.gif, hello_html_m465e5e5b.gif - произвольные целые числа.

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

hello_html_m7f8839c.gif

Разделим 5 на -4 с «остатком», hello_html_m6661883f.gif, преобразуем исходное уравнение к виду

hello_html_7fd59b01.gif.

Заменив hello_html_m34ccd7e9.gif получим hello_html_6695da1e.gif, следовательно

hello_html_m2f2ea4bb.gif, является решением данного ЛДУ.















6. Литература:


  1. Башмакова, И.Г. Диофант и диофантовы уравнения [Текст]. – М.: «Наука», 1972 г. - 68 с.

  2. Бухштаб, А. А. Теория чисел [Текст]. - М.: Государственное учебно-педагогическое издательство министерства просвещения РСФСР, 1960. - 378 с.

  3. Виноградов, И.М. Основы теории чисел: Учебное пособие. 11-е изд. [Текст]. – СПб.: Издательство «Лань», 2006. - 176 с.

  4. Гаусс, Карл Фридрих Труды по теории чисел. Под общей ред. Виноградова И.М. [Текст] – М.: Изд. академических наук СССР, 1959 г. - 980 с.

  5. Гельфонд, А.О. Решение уравнений в целых числах. Популярные лекции по математике, вып. [Текст]. М.: «Гостехиздат», 1957 г. - 66 с.

  6. Давенпорт, Г. Введение в теорию чисел [Текст]: Пер. с английского Мороза Б.З. под ред. Линника Ю.В. – М.: «Наука», 1965 г. - 176 с.

  7. Матисеевич, Ю.В. Десятая проблема Гильберта [Текст]. - М.: «Физматлит», 1973 г. - 224 с.

  8. Михелович, Ш.Х. Теория чисел [Текст]. – М.: «Высшая школа», 1962 г. - 260 с.

  9. Соловьев, Ю. Неопределенные уравнения первой степени [Текст]: Квант, 1992 г., №4.

  10. Стройк, Д.Я. Краткий очерк истории математики [Текст]. – М.: «Наука», 1990 г. - 256 с.



Исследовательская работа "Диофантовы уравнения"
  • Математика
Описание:

Введение. 2

1. Диофант и история диофантовых уравнений.2

2.  Число решений ЛДУ.4

3.  Нахождение решений для некоторых частных случаев ЛДУ.6

3.1. ЛДУ c одной неизвестной.6

3.2. ЛДУ с двумя неизвестными.6

4. Нахождение решений произвольного ЛДУ.10

5. Пример решения ЛДУ на TurboPascale.11

5.1 Алгоритм решения.11

5.2 Листинг программы на TurboPascale.12

5.3 Пример решения уравнения.13

6. Литература:14

 Введение.

Определение 1. Диофантовым уравнением 1-ой степени (линейным) с  неизвестными называется уравнение вида

 ,

где все коэффициенты и неизвестные – целые числа и хотя бы одно .

Для сокращения записи условимся далее сокращать фразу линейное диофантово уравнение, как ЛДУ.

Определение 2. Решением ЛДУ называется упорядоченная n-ка целых чисел , такая, что .

 

 

Автор Хамидуллина Лариса Васильевна
Дата добавления 04.01.2015
Раздел Математика
Подраздел
Просмотров 775
Номер материала 25643
Скачать свидетельство о публикации

Оставьте свой комментарий:

Введите символы, которые изображены на картинке:

Получить новый код
* Обязательные для заполнения.


Комментарии:

↓ Показать еще коментарии ↓