Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений»



Скачать 245.2 Kb.
страница2/3
Дата16.10.2012
Размер245.2 Kb.
ТипРеферат
1   2   3

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

Нами предложен еще один метод – метод сравнения по модулю (2.6). На наш взгляд он более рационален.





1. Теоретическая часть исследования

1.1 История диофантовых уравнений


Уравнения, в которых неизвестные величины выражаются целыми числами, называют диофантовыми (неопределенными) по имени математика Диофанта, жившего в III в. н. э. [см.: 5, с.42].

История сохранила нам мало черт биографии замечательного александрийского ученого. Достоверно известно лишь своеобразное жизнеописание Диофанта, которое по преданию было высечено на его надгробии и представляло задачу-головоломку: «Бог ниспослал ему быть мальчиком шестую часть жизни; добавив к сему двенадцатую часть, Он покрыл его щеки пушком; после седьмой части Он зажег ему свет супружества и через пять лет после вступления в брак даровал ему сына. Увы! Несчастный поздний ребенок, достигнув меры половины полной жизни отца, он был унесен безжалостным роком. Через четыре года, утешая постигшее его горе наукой о числах, он (Диофант) завершил свою жизнь». Решив уравнение, получим, что Диофант прожил 84 года.

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

Первое общее решение уравнения первой степени ах+by=c, где a, b,c – целые числа, встречается у индийского мудреца Брахмагупты (ок. 625 г.). Поэтому, строго говоря, нет оснований называть линейные неопределенные уравнения диофантовыми. Однако исторически все же сложилось применять термин «диофантово», к любому уравнению, решаемому в целых числах.

В 1624 г. публикуется книга французского математика Баше де Мезирьяка, в которой он для решения уравнения ах+by=c применяет процесс, сводящийся к последовательному вычислению неполных частных и рассмотрению подходящих дробей.

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

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

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

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

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


1.2 Общее решение линейных диофантовых уравнений

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

1.2.1 Однородные уравнения

Прежде всего, мы рассмотрим однородные линейные уравнения, т.е. уравнения вида ах + by = 0. Справедлива следующая теорема, которая дает полное решение диофантовых уравнений вида ах + by = 0.

Теорема 1. Если ax=by (a, b, x, y∈Z) и НОД(a, b)=1, то x, y можно представить в виде x=bt, y=at, где t — некоторое целое число.

Доказательство. Рассмотрим два случая:

1) b0. По условию (ax) b, НОД(a, b)=1; следовательно, x b, т. е. x=bt, где t∈Z. Тогда y= = =at.

2) b=0. Тогда a0, и исходное уравнение принимает вид ax=0, откуда x=0. Поскольку НОД(a,b)=1, то a=±1. Тогда, полагая t=, имеем: 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.
1.2.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 и 2202, поэтому данное уравнение имеет целочисленные решения.

б) НОД (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)=d1и с не делится на d, то уравнение целых решений не имеет.

2. Если НОД (а, b)=d1 и с делится на d, то разделить обе части уравнения ax+by=c на d, получив уравнение, в котором коэффициенты будут взаимно просты.

3. Найти (х0, у0) – частное решение одним из методов, которые рассмотрены во второй части.

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

х=х0c+bt, y=y0с – аt, где х0, у0 – целое решение уравнения ах+bу=1, t  Z.

2. Практическая часть исследования: методы решения линейных

диофантовых уравнений с двумя переменными

Таким образом, если известно какое-то одно (частное) решение уравнения (*), то можно записать и все остальные решения. Но как найти хотя бы одно частное решение? Если коэффициенты уравнения малы по модулю, то это решение бывает нетрудно подобрать.
2.1 Метод перебора

Рассмотрим суть метода на примере.

Задача 1. В аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд – по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных? [см.: 1, c. 163]

Решение. Пусть х – количество морских звёзд, у – количество осьминогов. Тогда у всех осьминогов 8у ног, а у всех звёзд 5х ног.

Составим уравнение: 5х + 8у = 39.

Заметим, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х – целое неотрицательное число, то и у= должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 – 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3.

Ответ: 3 осьминога и 3 морские звезды.

Если уравнение имеет целые решения, то перебрать их невозможно, так как таких решений бесконечное множество. При больших значениях коэффициентов подбор решений может оказаться также невыполнимой задачей (например, 121x−384y+716=0), поэтому необходим метод, позволяющий найти частное решение при любых значениях коэффициентов.


2.2 Метод, основанный на алгоритме Евклида

Теорема 3 дает решение диофантовых уравнений для случая НОД(а,b)= =1. А если НОД (а, b)1, то нужно разделить обе части уравнения на d. Поскольку сd (иначе по теореме 2 уравнение не имеет решение), то все коэффициенты останутся целыми, а поскольку НОД (, =1, то к полученному уравнению уже можно применить теорему 3. Рассмотрим нахождение частного решения и применение теоремы 3 на примере.

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

Решение.

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

2816 = 407·6 + 374;

407 = 374·1 + 33;

374 = 33·11 + 11;

33 = 11·3.

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

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

  2. С помощью алгоритма Евклида найдем линейное представление числа 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.

Следовательно, пара чисел х0 = – 83·3= –249 и у0 = – 12·3= – 36 есть частное решение уравнения 37х – 256y = 3.

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

х= – 249+256t, y= – 36+37t, где t  Z.

Ответ: х= – 249+256t, y= – 36+37t, где t  Z.

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

Задача 2. Автомобиль грузоподъёмностью 5 т нужно полностью загрузить контейнерами, имеющими массу 140 кг и 170 кг. Как это можно сделать? Укажите, сколько контейнеров каждого вида следует взять [см.: 3, с.24].

Решение. Пусть х – количество контейнеров массой 140 кг,

у – количество контейнеров массой 170 кг, тогда

140х+170у (кг) – грузоподъёмность автомобиля.

Известно, что грузоподъёмность 5т = 5000 кг.

Уравнение: 140х+170у = 5000, х, у  Z и х0, у0.

14х+17у=500, НОД (14,17)=1, значит, уравнение имеет корни в целых числах. Представим НОД(14,17)=1 в виде 14u+17v.

17=141+3, 3=17 – 141,

14=34+2, отсюда 2=14 – 34,

3=21+1, 1=3 – 21.

2=12.

1=3 – 21=3 – (14 – 34)1= – 14+35= – 14+(17 – 141)5= – 146+175.

5001= 500(– 146+175)= – 143000+172500, значит, частное решение

х0= – 3000, у0= 2500. Общее решение: х = – 3000 – 17t, у = 2500 + 14t, t Z.

Так как x и y неотрицательные целые числа, то чтобы найти значение t, решим систему неравенств:

   учитывая, что t Z, получим: t1= –178, t2= –177.

Тогда х1= – 3000 – 17(–178)=26, у1= 2500 + 14(–178)=8,

х2= – 3000 – 17(–177)=9, у2= 2500 + 14(–177)=22.

Ответ: 1) 26 контейнеров по 140 кг и 8 контейнеров по 170 кг;

2) 9 контейнеров по 140 кг и 22 контейнеров по 170 кг.
1   2   3

Похожие:

Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового Века» 2012 Гуманитарные науки (от 14 до 17 лет)
Болховитинова Юлия,16 лет Руководитель Водопьянова Татьяна Михайловна
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового века»-2012 Точные науки ( от 11 – 13 лет) «Черные дыры Вселенной»
«черная дыра»? Где их можно обнаружить? Как они образуются? Большинство астрофизиков верит в реальное существование черных дыр. Но...
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового Века» 2012 Гуманитарные науки (от 14 до 17 лет) «Антропонимические традиции армян г. Волгограда»
Изучение имён собственных волгоградской молодёжи и старшего поколения
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового Века» Номинация: Гуманитарные науки (от 14 до 16 лет) Жизнь неба: от античности до наших дней

Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового Века» 2012 Гуманитарные науки (от 14 до 17 лет) «Метафора – выразительное средство в мышлении и действии»
Неумение использовать художественные средства становится причиной стилистического несовершенства в речи учеников, поэтому вся работа,...
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового Века» 2012 Художественная проза (от 7 до 9 лет)
Жили были солнышко и художник Карандаш Рисовалкин. Они были очень хорошими друзьями. Солнышку нравились картины Карандаша, а Карандаш...
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconПрограмма по курсу «Линейная алгебра», 2 семестр 2011/2012 учебного года повышенный уровень
Системы линейных уравнений. Алгоритм Гаусса упрощения системы линейных уравнений и матрицы. Главные и свободные неизвестные. Разложение...
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный фестиваль «Звёзды Нового Века»-2012 Гуманитарные науки (от14-до17лет) Подводники Балтийского флота в годы Великой Отечественной войны
В послевоенные годы при издании книг ему оказывали поддержку известные военачальники, в том числе военачальники вмф. В нашей семье...
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconМеждународный Фестиваль «Звезды Нового Века»
Марчук Эдуард Викторович, канд физ мат наук, учитель физики моу лицея №8: Олимпия
Международный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений» iconТочные решения обобщенных уравнений типа рассматривается класс уравнений типа
Рассматривается класс уравнений типа. Используя переменную бегущей волны и метод простейших уравнений, построены точные решения для...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org