Учебный проект " Алгоритм Евклида"

Проект по теме: Алгоритм Евклида и линейные диофантовы уравнения.

Выполнила: ученица 8 Б класса Лубенец Полина

Руководитель: Валентина Павловна Затеева

План:

Актуальность .

Цель .

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

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

1. Алгоритм Евклида. Линейное диофантово уравнение и 4 способа его решени.

2. Метод прямого перебора.

3. Метод разложения на множители.

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

5. Метод решения относительно одной переменной.

6. Метод спуска.

7. Использование цепных дробей.

8. Метод оценки.

Заключение .

Список литературы.

Актуальность темы.

Актуальность данной темы обусловлена тем, что владение

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

позволяет преодолеть встречающиеся трудности и

приводить к реальным результатам в теории чисел.

Цель и задачи проекта:

Цель.

~Изучить способы решения диофантовых уравнений;

~Повысить уровень математической культуры, прививая навыки самостоятельной исследовательской работы в математике.

Задачи.

~Показать методы решения Диофантовых уравнений;

~Показать практическую значимость методов

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

~Раскрыть понятие

диофантовых уравнений на примере доказательств

теорем и применения их при решении задач;

~Показать , что использование конкретного

метода приводит к наиболее простому решению

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

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

Решение уравнений в целых числах является одной из древнейших математических задач. Наибольшего расцвета эта область математики достигла в Древней Греции. Основным источником, дошедшим до нашего времени, является произведение Диофанта – «Арифметика». Диофант суммировал и расширил накопленный до него опыт решения неопределенных уравнений в целых числах.

В истории сохранилось мало фактов биографии замечательного александрийского ученого-алгебраиста Диофанта. По некоторым данным Диофант жил до 364 года н.э.

Гипотеза.

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

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

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

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

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

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

Рассмотрим пример.  Найти НОД (645; 381).

Решение.

Разделим с остатком 645 на 381. Мы получим: 645=381·1+264.

Далее разделим с остатком 381 на 264, получим: 381=264·1+117.

Теперь разделим с остатком 264 на 117, получим: 264=117·2+30.

Продолжим процесс деления, разделим с остатком 117 на 30, получим: 117=30·3+27. Далее, 30=27·1+3. Следующий шаг – делим 27 на 3, получаем, что 27=3·9 +0, т. е. 27 делится на 3 без остатка. Значит, наибольший общий делитель чисел 27 и 3 равен 3, следовательно, и наибольший общий делитель чисел 645 и 381 равен 3, т. е. последнему отличному от нуля остатку.

Таким образом, НОД (645; 381) = 3.

Прием разыскания наибольшего общего делителя, примененный в этом примере, и представляет собой алгоритм Евклида.

Линейное диофантово уравнение и 4 способа его решения.

Правило 1. Если с не делится на d, то уравнение ах + ву = с не имеет решений в целых числах. Н.О.Д.(а,в) = d.

Правило 2. Чтобы найти решение уравнения ах + ву = с при взаимно-простых а и в, нужно сначала найти решение (Х о  ; у о ) уравнения ах + ву = 1; числа СХ о  , Су о  составляют решение уравнения ах + ву = с.

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

5х - 8у = 19 … (1)

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

Знаем, что если Н.О.Д.(а;в) =1, т.е. а и в взаимно-простые числа, то уравнение (1)

имеет решение в целых числах х и у. Н.О.Д.(5;8) =1. Методом подбора находим частное решение: Х о  = 7; у о  =2.

Итак, пара чисел (7;2) - частное решение уравнения (1).

Значит, выполняется равенство: 5 x 7 – 8 x 2 = 19 … (2)

Вопрос: Как имея одно решение записать все остальные решения?

Вычтем из уравнения (1) равенство (2) и получим: 5(х -7) – 8(у - 2) =0.

Отсюда х – 7 =  . Из полученного равенства видно, что число (х – 7) будет целым тогда и только тогда, когда (у – 2) делится на 5, т.е. у – 2 = 5n, где n какое-нибудь целое число. Итак, у = 2 + 5n, х = 7 + 8n, где n   Z.

Тем самым все целые решения исходного уравнения можно записать в таком виде:

  n   Z.

Второй способ . Решение уравнения относительно одного неизвестного.

Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент.

5х - 8у =19    х = 

Остатки при делении на 5: 0,1,2,3,4. Подставим вместо у эти числа.

Если у = 0, то х =  = .

Если у =1, то х =  = .

Если у = 2, то х =  =  = 7   Z.

Если у =3, то х =  = .

Если у = 4 то х =   = .

Итак, частным решением является пара (7;2).

Тогда общее решение:   n   Z.

Третий способ . Универсальный способ поиска частного решения.

Для решения применим алгоритм Евклида. Мы знаем, что для любых двух натуральных чисел а, в, таких, что Н.О.Д.(а,в) = 1 существуют целые числа х,у такие, что ах + ву = 1.

План решения:

• Сначала решим уравнение 5m – 8n = 1 используя алгоритм Евклида.

2. Затем найдем частное решение уравнения (1)по правилу 2.

3. Запишем общее решение данного уравнения (1).

• Найдем представление: 1 = 5m – 8n. Для этого используем алгоритм Евклида.

8 = 5   1 + 3.

5 = 3 

3 = 2  .

Из этого равенства выразим 1. 1 = 3 - 2   = 3 – (5 - 3  )  =

= 3 - 5  = 3  = (8 – 5   - 5  8 2 - 5 1=

= 5 ( -2). Итак, m = -3, n = -2.

2. Частное решение уравнения (1): Х о  = 19m; у о  =19n.

Отсюда получим: Х о  =19 ; у о  = 19

  .

Пара (-57; -38)- частное решение (1).

3. Общее решение уравнения (1):   n   Z.

Четвертый способ.  Геометрический.

План решения.

1. Решим уравнение 5х – 8у = 1 геометрически.

2. Запишем частное решение уравнения (1).

3. Запишем общее решение данного уравнения (1).

1

Отложим на окружности последовательно друг за другом равные дуги, составляющие

  -ю часть полной окружности. За 8 шагов получим все вершины правильного

вписанного в окружность 8-угольника. При этом сделаем 5 полных оборотов.

На 5 – ом шаге получили вершину, соседнюю с начальной, при этом сделали 3 полных

оборота и еще прошли   - ю часть окружности, так что х      = у + 

.

Итак, Х о  = 5, у о  =3 является частным решением уравнения 5х – 8у = 1.

2. Частное решение уравнения (1): Х о  = 19  у о  =19 

3. Общее решение уравнения (1):   n   Z.

у, соседн

Метод прямого перебора.

Задача:

• На складе имеются гвозди в яиках по 16, 17 и 40 кг. Может ли кладовщик выдать 100 кг гвоздей, не вскрывая ящик?

17х+40у+16z=100 Ответ: да, может 4 ящика по 17 кг и 2 ящика по 16 кг.

Задача:

• На 5 рублей куплено 100 штук разных фруктов. Цены на фрукты таковы: арбуз 1 штука 50 коп, яблоко 1 штука 10 коп, слива 1 штука 1 коп. Сколько фруктов каждого рода было куплено?

Ответ: 1 арбуз, 39 яблок, 60 слив

Метод разложения на множители.

~вынесение множителя за скобку;

~использование формул сокращённого умножения;

~способ группировки;

~предварительное преобразование.

Задача 2. Решите уравнение в целых числах : 3ху + 2х + 3у = 0 Решение: 3ху + 2х + 3у + 2 = 2 3у ( х + 1) + 2 ( х + 1) = 2 (3у + 2)( х + 1) = 2 3у + 2 = 2 х + 1 = 1 3у + 2 = 1 х + 1 = 2 3у + 2 = -2 х + 1 = - 1 3у + 2 = -1 х + 1 = -2 Решите системы и отберите целые решения 18 Ответ: (0;0); (-3; -1)

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

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

Пример.

Решить уравнение в целых числах x+ y= 4(x y+ xy + 1).

Перепишем исходное уравнение в виде (x+ y)= 7(x y+

хy ) + 4. Так как кубы целых чисел при делении на 7 дают

остатки 0, 1 и 6, но не 4, то уравнение неимеет решений в

целых числах.Ответ: целочисленных решений нет.

3

2

2

3

2

Метод решения относительно одной переменной.

Метод решения относительно одной переменной.

• выделение целой части;
• использование дискриминанта (неотрицательность);
• решение уравнений в целых числах как квадратных относительно какой-либо переменной.

Метод (бесконечного) спуска.

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

задачи этот процесс должен на чём-то закончиться.

Часто метод бесконечного спуска применяется в более простой форме.

Предположив, что мы уже добрались до естественного конца, видим, что

«остановиться» не можем.

ПРИМЕР:

5x3+11y3+13z3=0. Имеем сравнение: 5x3+11y3=0(13).

Так как a3=0;1;5;8;12(13), то число 5x3+11y3делится на 13 тогда и

только тогда, когда x=y=0(13). Поэтому x=13x1, y=13y1,z=13z1 .

Подставив в уравнение, получим: 5x13+11y13+13z13=0.

Продолжая этот процесс, получим, что числа x,y,z делятся н любую натуральную степень числа 13. Это возможно лишь при условии, когда x=y=z=0.

ПРИМЕР 1:

Найти все целые решения:

50x-42y=34/:2 (1)

25x-21y=17 (2) (1)(2)

(25,21)=1, (1) имеет бесконечное множество решений.

x=x0+21t,

y=y0+25t, t[-Z

Найдем x0,y0.

Уравнение (2) можно свести к сравнению первой степени:

25x=17(21)

4x= -4(21) /:4, так как (4;21)=1;

Имеем:

x= -1(21), то есть x=20(21);

Значит, x0=20

21y=25x-17 y=(25*20-17):21=23, y0=23

Решение: x=20+21t,

y=23+25t; t[-Z

Вместо 20 можно было взять -1

ПРИМЕР 2:

3x+4y=13 (*)

Аналогично предыдущему примеру1 , из уравнения имеем:

3x=1(4). Откуда x=3(4) , то есть x=3+4t, t[-Z. Подставляя в

уравнение, найдем y=1-3t. Множество решений:

{(3+4t,1-3t);t[-Z}.

ПРИМЕР 3:

5x3+11y3+13z3=0. Имеем сравнение: 5x3+11y3=0(13).

Так как a3=0;1;5;8;12(13), то число 5x3+11y3делится на 13 тогда и

только тогда, когда x=y=0(13). Поэтому x=13x1, y=13y1,z=13z1 .

Подставив в уравнение, получим: 5x13+11y13+13z13=0.

Продолжая этот процесс, получим, что числа x,y,z делятся н любую натуральную степень числа 13. Это возможно лишь при условии, когда x=y=z=0.

Цепная дробь.

Цепная дробь Пусть α0 и α1 – натуральные числа. Для нахождения их наибольшего общего делителя используется алгоритм Евклида последовательного деления с остатком: α0 = a0α1 + α2, α1 = a1α2 + α3, α2 = a2α3 + α4, . . . где натуральные числа a0, a1, a2, . . . суть неполные частные. Это алгоритм разложения числа α = α0/α1 в правильную цепную дробь [1], и он применим к любым вещественным числам α. При этом a0 = [α], где [α] – целая часть числа

Использование цепных дробей.

Теорема: Если а и b- целые числа, причем b, то можно, всегда найти такое целое число q, что а= bq+ г, где r- целое число, удовлетворяющее неравенству 0

Отсюда как следствие можно вывести метод для нахождения наибольшего общего делителя двух чисел. Он основан на том обстоятельстве, что из соотношения вида а= bq+r следует, что (а,b)=(b,r).

В самом деле, всякое число u, которое одновременно делит и а, и b, т.е. а = su, b =tu, делит также и r, т.к. r = а - bq= su - qtu = (s - qt}и. И обратно, всякое число v, которое

одновременно делит bи r, т.е., b= s’v, r=t’v, делит также и а, т.к. а = bq+r= s’vq+t’v= =(s’q+t’)v.

Значит, каждый общий делитель чисел а иbесть и общий делитель чисел bи r, то ясно, что наибольший общий делитель а и bдолжен совпадать с наибольшим общим делителем чисел bи r.

Пример: Найти НОД чисел 1804 и 328.

Обыкновенное «длинное» деление приводит к заключению, что 1804 = 53X28 + 164. В силу (2) следует, что (1804, 328) = (328, 164). Таким образом, задача вычисления НОД (1804, 328) заменена теперь аналогичной задачей, но зависящей теперь от меньших чисел. Если продолжим эту процедуру, то получим 328 = 2X164 + 0, т.к. (328, 164)=(164, 0)=164. Значит, НОД (1804, 328) = 164.

Метод оценки.

• Использование известных неравенств

неравенство Коши

• Приведение к сумме неотрицательных выражений

(х1 – а1)2 + (х2 – а2)2 + …+(хп – ап)2 = с

Заключение.

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

Список использованной литературы:

• Вагутен В.Н Алгоритм Евклида и основная теорема арифметики// Квант. – 1972. - №6
• Гельфонд А.О. Решение уравнений в целых числах. – М.: Наука, 1978. – (Популярные лекции по математике).
• Михайлов И.О диофантовом анализе// Квант. – 1980. - №6
• Факутальтативный курс по математике. 7-9/ сост. И.Л Никольская. – М.: Просвещение, 1991.
• http:// dodiplom.ru/ready/129004 Реферат: Диофантовы уравнения.