Международный Фестиваль «Звезды Нового Века» icon

Международный Фестиваль «Звезды Нового Века»



Смотрите также:
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века» Гороскоп Фестиваль...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...
Международный Фестиваль «Звезды Нового Века»...



скачать
Международный Фестиваль «Звезды Нового Века» - 2012

Точные науки (от 14 до 17 лет)


«Исследование методов решения

линейных диофантовых уравнений»

(математика)


Автор работы: Храмова Екатерина,

15 лет, ученица 8 класса


Руководитель: Леонова Татьяна Ивановна,

учитель математики


Республика Мордовия,

г. Саранск, МОУ «Лицей №7»


2011 г.

Содержание





Введение

3

1

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

5

1.1

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

5

1.2

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

7

1.2.1

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

7

1.2.2

Общие линейные уравнения

7

2

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


10

2.1

Метод перебора

10

2.2

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

11

2.3

Метод спуска

13

2.4

Метод цепных дробей

14

2.5

Метод остатков

15

2.6

Метод сравнения по модулю

15

3

Линейные уравнения с тремя переменными

16




Заключение

Список использованных источников

Приложение 1

Приложение 2

17

18

19

21


Введение

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

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

Объектом исследования данной работы является неопределенные линейные (диофантовы) уравнения с двумя переменными, т.е. уравнение вида ax+by=с, где a, b, с Z, для которого поставлена задача поиска решений в целых числах.

Проблема состоит в следующем: дано линейное диофантово уравнение (ЛДУ), как определить – имеет ли оно решения в области целых чисел, и если имеет, то как их найти наиболее эффективно?

Гипотеза: существует общий алгоритм решения линейных диофантовых уравнений.

^ Цель работы: выявить наиболее эффективный метод решения линейных диофантовых уравнений.

Поставленная цель требует решения следующих задач:

  • выяснить, всегда ли ЛДУ имеет целочисленные решения;

  • сформулировать алгоритм, позволяющий найти все решения ЛДУ;

  • рассмотреть различные методы поиска частного решения ЛДУ;

  • решить текстовые задачи, описывающие различные практические ситуации, математической моделью которых являются диофантовы уравнения первой степени;

  • решить ЛДУ с тремя неизвестными.

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

^

Нами предложен еще один метод – метод сравнения по модулю (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 кг.


^ 2.3 Метод спуска

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

Пример 4. Решить в целых числах уравнение 5x + 8y = 39.

Решение. НОД (5,8)=1, следовательно, уравнение имеет решение в целых числах.

  1. Выберем неизвестное, имеющее наименьший коэффициент (в нашем случае это х), и выразим его через другое неизвестное: . Выделим целую часть: . Очевидно, что х будет целым, если выражение окажется целым, т.е. число 4 – 3y без остатка делится на 5.

  2. Введем дополнительную целочисленную переменную z следующим образом: 4 –3y = 5z. В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами. Решать его будем уже относительно переменной y, рассуждая точно также как в п.1: . Выделяя целую часть, получим: . Рассуждая аналогично предыдущему, вводим новую переменную u: 3u = 1 – 2z.

  3. Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z: = . Требуя, чтобы было целым, получим: 1 – u = 2v, откуда u = 1 – 2v. Дробей больше нет, спуск закончен.

  4. Теперь необходимо «подняться вверх». Выразим через переменную v сначала z, потом y и затем x: z = = = 3v – 1;

= 3 – 5v; = = 3+8v.

  1. Формулы x = 3+8v и y = 3 – 5v, где v Z, представляют общее решение исходного уравнения в целых числах.

Ответ: x = 3+8v и y = 3 – 5v, где v Z.


^ 2.4 Метод цепных дробей

Для решения следующей задачи используются цепные дроби (См.: Приложение 2).

Задача 3. Для газификации жилого дома требуется проложить газопровод протяженностью 150 м. Имеются трубы 13 м и 9 м длиной. Сколько требуется труб, чтобы не приходилось их разрезать при прокладке газопровода.

Решение. Для ответа на вопрос задачи требуется решить диофантово уравнение 9х+13у=150.

  1. Представим дробь в виде конечной цепной дроби:

=[0;1,2,4].

  1. Составим подходящие дроби:

3. Запишем общее решение уравнения:



4. t= – 34.

5. x=8, у=6.

Ответ: потребуется 8 труб по 9 м и 6 – по 13 м.

^ 2.5 Метод остатков

Этот метод основан на исследовании возможных остатков левой и правой частей уравнения от деления на некоторое фиксированное натуральное число. Рассмотрим пример, который раскрывает сущность данного метода.

Многие «математические фокусы» основаны на методах решения неопределенных уравнений. Например, фокус с угадыванием даты рождения.

Предложите Вашему знакомому угадать его день рождения по сумме чисел равных произведению даты его рождения на 12 и номера месяца рождения на 31. Для того чтобы угадать день рождения Вашего знакомого нужно решить уравнение: 12х + 31y = с.

Решение. Пусть Вам назвали число 284, т.е. имеем уравнение 12х + 31y = 284. Для того чтобы найти х и y можно рассуждать так: число 12х + 24y делится на 12, следовательно, по свойствам делимости, числа 7y и 284 должны иметь одинаковые остатки при делении на 12. Число 284 при делении на 12 дает остаток 8, следовательно, 7y при делении на 12 тоже должно давать в остатке 8, а так как y – это номер месяца, то 1 ≤ y ≤ 12, следовательно, y=8. Теперь нетрудно найти х=3. Таким образом, Ваш знакомый родился 3 августа.

Ответ: 3августа.

^ 2.6 Метод сравнения по модулю

Рассмотренный выше метод натолкнул на мысль «нельзя ли записать решение короче, используя математический язык?». Решим задачу из пункта 2.5, используя сравнения по модулю [см.: 3, с.10–12].

Решение. НОД (12, 31)=1, 12х – 284= – 31у. Найдем решение сравнения 12х284 (mod 31), 3х71 (mod 31), 3х9 (mod 31), х3 (mod 31), х=3. Тогда у=(284 – 123):31=8.

Ответ: 3 августа.

Используя сравнение по модулю, решим задачу 3 из пункта 2.4.

Задача 3. Для газификации жилого дома требуется проложить газопровод протяженностью 150 м. Имеются трубы 13 м и 9 м длиной. Сколько требуется труб, чтобы не приходилось их разрезать при прокладке газопровода.

Решение. Решим уравнение 9х+13у=150 или 9х – 150= –13у. Рассмотрим сравнение 9х150 (mod 13), 3х50 (mod 13), 3х24 (mod 13), х8 (mod 13).

Следовательно, х0=8 и, учитывая, что х при делении на 13 дает остаток 8, получим общее решение: х=8+13t, где tZ. Исходя из условия 0х, получим, что х=8, тогда 98+13у=150, у=6.

Ответ: потребуется 8 труб по 9 м и 6 – по 13 м.

Сравнивая, решение двух задач приходим к выводу, что используя сравнение по модулю, получили более рациональное решение.


^ 3. Линейные уравнения с тремя переменными

Пример 4. Решить в целых числах уравнение 4x – 6y + 11z = 7.

Решение. Разделив с остатком –6 на 4, получим –6 = 4(–2) + 2. Представим исходное уравнение в виде 4(x – 2y) + 2y + 11z = 7.

После замены, а = x – 2y, это уравнение запишется следующим образом 4а + 2y + 11z = 7. Учитывая, что 11 = 2·5 + 1, преобразуем последнее уравнение: 4а + 2(y + 5z) + z = 7. Положив b = y + 5z, получим 4a + 2b + z = 7.

Это уравнение имеет следующее решение: a, b – произвольные целые числа, z = 7 – 4a – 2b. Следовательно, y = b – 5z = 20a + 11b – 35, x = a + 2y = = 41a+ 22b – 70.

Таким образом, решение исходного уравнения имеет вид: x = 41a+ +22b – 70, y = 20a + 11b – 35, z = 7 – 4a – 2b, где a, b – произвольные целые числа.

Ответ: x = 41a+ 22b – 70, y = 20a + 11b – 35, z = 7 – 4a – 2b, где a, b  Z.

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

Заключение

В ходе выполнения работы был получен ответ на вопрос о разрешимости неопределенных (диофантовых) уравнений первой степени в целых числах.

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

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

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

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

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


Список использованных источников

1. Аксёнова, М.Д. Энциклопедия для детей Т. 11 (Математика) / М. Д. Аксёнова – М.: «Аванта +», 1998. – 688 с.

2. Виленкин, Н. Я. За страницами учебника математики 10 – 11 класс. / Н.Я. Виленкин – М.: Просвещение, 1996. – 319 с.

3. Деревянкин, А.В. Числа и многочлены: Методическая разработка для учащихся заочного отделения МММФ / А.В. Деревянкин. – М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2008. – 72 с.: ил.

4. Матисеевич, Ю.В. Десятая проблема Гильберта / Ю.В. Матисеевич. – М.: «Физмат лит», 1973. – 224 с.

5 Никольская, И.Л. Факультативный курс по математике: учеб. пособие 7–9 кл. сред. шк. / И.Л. Никольская. М.: Просвещение, 1991. – 383 с.: ил.

6. Стройк, Д.Я. Краткий очерк истории математики / Д.Я. Стройк. – М.: «Наука», 1990 г. – 256 с.


Приложение 1

Алгоритм Евклида

Чтобы найти наибольший общий делитель двух данных натуральных чисел можно действовать по определению: выписать все делители этих чисел, выделить среди них общие и выбрать среди всех общих делителей наибольший. Но этот способ можно порекомендовать лишь для совсем небольших чисел, поскольку он весьма трудоёмок. А если надо найти НОД(41450, 3687135)? В таких случаях гораздо более эффективным оказывается алгоритм Евклида. Действие алгоритма Евклида основано на приведённых ниже лемме и теореме.

Лемма. Для любых двух целых чисел a и b, хотя бы одно из которых не равно нулю, верно равенство НОД(a, b)=НОД(a−b, b).

Доказательство. Покажем, что множество M общих делителей чисел a и b совпадает с множеством N общих делителей чисел a−b и b. Пусть m — произвольный общий делитель чисел a и b. Тогда (a−b)m, т. е. m является общим делителем чисел a−b и b.

Обратно, пусть n – произвольный общий делитель чисел a−b и b. Тогда a=((a−b)+b)n, т. е. n является общим делителем чисел a и b.

Таким образом, множество M общих делителей чисел a и b совпадает с множеством N общих делителей чисел a−b и b; следовательно, и наибольшие элементы этих двух множеств (т.е. НОД(a, b) и НОД(a−b, b)) совпадают, что и требовалось доказать.

Докажем теорему, которая является обобщением леммы.

Теорема. Пусть a=qb+r, где a, b, q, r∈Z, причём хотя бы одно из чисел a, b не равно нулю. Тогда НОД(a, b)=НОД(b, r).

Доказательство. В соответствии с леммой выполним следующие переходы: НОД(a,b)=НОД(a−b,b)=НОД((a−b)−b,b)=НОД(a−2b,b)=...=НОД(a−qb, b)= НОД (r, b)=НОД(b, r), что и требовалось доказать [см.: 3, с. 15–16].

Итак, чтобы найти наибольший общий делитель двух чисел:

1) надо большее из двух чисел разделить на меньшее;

2) потом меньшее из чисел на остаток при первом делении;

3) затем остаток при первом делении на остаток при втором делении и вести этот процесс до тех пор, пока не произойдет деление без остатка. Последний отличный от нуля остаток и есть искомый НОД двух данных чисел.

Пример. Найдите НОД(1014, 273).

Решение. Выполним ряд делений с остатком: 1014=273·3+195; 273=195·1 +

+78; 195=78·2+39; 78=39·2. По алгоритму Евклида НОД(1014, 273)=

=НОД (273, 195)=НОД (195, 78)= =НОД (78, 39)=39.

Ответ: 39.

Приложение 2

Понятие цепной дроби. Представление рациональных чисел

в виде цепной дроби

Обратимся к алгоритму Евклида. Из равенства a=bq0+r1 вытекает, что дробь можно записать в виде суммы целой части и правильной дроби: . Из второго равенства b=r1q1+r2 имеем. Значит, . Продолжим этот процесс до тех пор, пока не придём к знаменателю qn. В результате мы представим обыкновенную дробь в следующем виде: .

Эйлер назвал дробь, стоящую в правой части равенства непрерывной. Приблизительно в тоже время в Германии появился другой термин – цепная дробь. Так за этими дробями и сохранились оба названия. Ввиду громоздкости развёрнутой записи цепной дроби применяют компактную запись

= [q0; q1, q2, …, qn].

Пример. Представить рациональное число в виде цепной дроби.

Решение. .

Очевидно, что любое рациональное число, и только оно записывается в виде конечной цепной дроби. Иррациональным числам соответствуют бесконечные цепные дроби.

Если при построении цепной дроби остановиться на знаменателе qk , то получиться дробь [q0; q1, q2, …, qк], которую называют к-й подходящей дробью для искомой и обозначают Найдем вид некоторых подходящих дробей:

Для рационального числа последовательность подходящих дробей конечна, и ее последний элемент [см.: 2, c. 79 – 81].

^ Формулы для решения уравнений вида ах+by=c

с использованием цепной дроби

Теорема. Общее решение в целых числах уравнения ах+bу=с (*) , где а, b, с – целые числа, отличные от нуля и НОД (а, b)=1 , можно представить в виде

, ,

где t – произвольное целое число, а и – числитель и знаменатель предпоследней подходящей дроби разложения числа в цепную дробь.

Доказательство. Пусть = – разложение числа в цепную дробь, а (s=1,2,…,n) – подходящие дроби этого разложения. Тогда =. По условию дробь – несократимая и дробь также несократимая, поэтому , . По свойству подходящих дробей , то есть . Умножив обе части последнего равенства на , получим равенство . Это равенство означает, что пара чисел и является целым решением уравнения (*).

Итак, для решения уравнения ax + by = c, где a, b, cцелые коэффициенты, способом «цепной дроби» нужно:

  1. представить дробь в виде конечной цепной дроби: = ;

  2. записать подходящие дроби;

  3. найти решение уравнения по формулам







Скачать 276,92 Kb.
оставить комментарий
работы
Дата07.08.2012
Размер276,92 Kb.
ТипРеферат, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх