Проект Алгоритм Евклида и Линейные диофантовы уравнения. Шпак Данил 8б

Муниципальное автономное образовательное учереждение «Образовательный центр имени М.М.Расковой»

ПРОЕКТ

Тема: «Алгоритм Евклида и линейные диофантовы уравнения»

Автор работы:

Шпак Данил Александрович,8 Б

Руководитель:

Затеева Валентина Павловна

Содержание проекта:

Введение……………………………………………………………………………………………………………………………………………….…2

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

Цель ………………………………………………………………………………………………………………………………………………………..3

Гипотеза………………………………………………………………………………………………………………………………………………….3

Задачи……………………………………………………………………………………………………….…………………………………………...3

Описание алгоритма Евклида и его доказательство………………………………………………………………….………..3

Пример использования алгоритма Евклида…………………………………………………………….………………………….4

Расширенный алгоритм Евклида………………………………………………………………………………………….………………5

Линейные диофантовы уравнения………………………………………………………………………………………………….…..5

Правила решения диофантовых уравнений………………………………………………..………………………………………5

Спосбоы решения линейного диофантового уравнения…………………………………………………………………….5

Заключение……………………………………………………………………………………………………………………………………………7

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

Введение.

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

        Есть замечательный способ отыскания Н.О.Д. без какой бы ни было предварительной обработки чисел. Такой способ придумали древнегреческие ученые более двух тысяч лет тому назад. Он носит название «алгоритм Евклида». О жизни греческого математика Евклида достоверные данные не известны. Считается, что он жил в III в. до н.э. в г.Александрии. Конечно, как и о других великих людях, о нем известно немало легенд, одна из которых очень поучительна. Египетский царь Птолемей  I спросил Евклида, нет ли более короткого пути для понимания геометрии, чем тот, который содержится в «Началах» (в современном издании эта книга имеет более 500 станиц, и, конечно, для ее изучения нужно немало времени и усердия). Евклид гордо ответил Птолемею, что «в геометрии нет царской дороги». Евклиду принадлежит выдающееся научное произведение, называемое «Начала». Оно состоит из 13 книг и излагает основы всей древнегреческой математики: элементарной геометрии, арифметики, методов определения площадей, объемов тел. Арифметике посвящены 7, 8, 9-я книги «Начал». Именно здесь и описывается алгоритм Евклида .

Актуальность темы проекта:

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

Цель проекта – Изучить способы решения диофантовых уравнений и разобраться в строении алгоритма Евклида.

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

Цель и гипотеза проекта обусловили следующие задачи:

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

2. Продемонстрировать алгоритм Евклида.

Описание алгоритма Евклида и его доказательство.

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). 

Пусть  a{\displaystyle a} и b{\displaystyle b} — целые числа, не равные одновременно нулю, и последовательность чисел

abr₁r₂r₃r₄r_n

определена тем, что каждое {\displaystyle r_{k}}r_k — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

{\displaystyle a=bq_{0}+r_{1},} a=bq₀ + r₁,

{\displaystyle b=r_{1}q_{1}+r_{2},} b=q₁r_{1 +}r₂,

r₁=r₂q₂+r₃,

…

r_k-2=r_k-1q_k-1+r_n,

…

r_n-2=r_n-1q_n-1+r_n,

r_n-1=r_nq_n.

{\displaystyle \cdots }

{\displaystyle r_{n-2}=r_{n-1}q_{n-1}+r_{n},}

{\displaystyle r_{n-1}=r_{n}q_{n}.}

Тогда Н.О.Д.(a, b), наибольший общий делитель a и b, равен r_n, последнему ненулевому члену этой последовательности.

Существование таких r₁, r₂, …, r_n, то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается для всех натуральных чисел  m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

I. Пусть a = b⋅q + r, тогда Н.О.Д. (a, b) = Н.О.Д. (b, r).

Доказательство:

1. Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда a = t₁⋅k и b = t₂⋅k, где t₁ и t₂ — целые числа из определения.

2. Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а {\displaystyle r=a-b\cdot q=(t_{1}-t_{2}\cdot q)\cdot k}r=a-b*q=(t₁-t₂*q)k (выражение в скобках есть целое число, следовательно, k делит r без остатка).

3. Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b.

4. Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот.

5. В частности, наибольший общий делитель остаётся тем же самым, так как в предположении, что Н.О.Д. (a, b) НОД (b, r) или Н.О.Д. (a, b) b, r) получаются противоречия, следовательно, Н.О.Д. (a, b) = Н.О.Д. (b, r). Что и требовалось доказать.

II. Н.О.Д.(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число).

Пример использования алгоритма Евклида.

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q₀ = 2), оставаясь с остатком 147:

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q₁ = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q₂ = 7), оставаясь без остатка:

147 = 7 × 21 + 0.

Таким образом последовательность a b  r₁  r₂  r₃  …  r_n в данном конкретном случае будет выглядеть так:

1071 462 147 21.

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и Н.О.Д.(1071, 462) = 21.

В табличной форме шаги были следующие:

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

Расширенный алгоритм Евклида.

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

Формулы для r_i могут быть переписаны следующим образом:

r₁₌a+b(-q₀)

r₂=b-r₁q₁=a(-q₁)+b(1+q₁q₀)

.

.

.

Н.О.Д.(a,b)=r_n=as+bt

Здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу.

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

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

ax + by =c,

где a, b, c — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типа. Сначала с помощью этого алгоритма можно определить d = НОД(a, b). Затем, используя расширенный алгоритм Евклида, определяются такие k и l, что:

ak+bl=d.

То есть x = k и y = l — это частное решение уравнения при c = d. Получается, что если c = q⋅d, то x = q⋅k, y = q⋅l — частное решение исходного уравнения, так как:

{\displaystyle a\cdot x+b\cdot y=a\cdot (q\cdot k)+b\cdot (q\cdot l)=q\cdot (a\cdot k+b\cdot l)=q\cdot d=c.}ax+by=a(qk)+b(ql)=q(ak+bl)

Обратно, если существует хотя бы одно решение уравнения, то c кратно d. Это следует из того, что d делит и a, и b (а значит, и всю левую часть), поэтому должно делить и c (правую часть). Таким образом, линейное диофантово уравнение имеет хотя бы одно решение тогда и только тогда, когда c кратно НОД(a, b).

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

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

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

Спосбоы решения линейного диофантового уравнения.

Все способы решения я буду демонстрировать на уравнении:

5х - 8у = 19 (1)

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

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

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

x₀= 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   5x=8y + 19  x=

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8 = 5 × 1 + 3.

5 = 3 × 1 + 2.

3 = 2 × 1 + 1.

Из этого равенства выразим 1.

1 = 3 - 2 × 1 = 3 – (5 - 3 × 1) ×  1 = 3 – 5 ×  1 + 3 × 1= 3 ×  2 – 5 × 1= (8 – 5 ×  1 ) × 2 – 5 ×  1 = 8 × - 5 × 2 -5 ×

1 = 5 × (-3) – 8 × (-2).

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

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

Отсюда получим: x_о =19 × (-3) = - 57 ; у_о =19  × (-2) = -38.

Пара (-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 × 5 = 95 у_о =19 × 3 = 57

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

Заключение.

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

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

• Вагутен В.Н Алгоритм Евклида и основная теорема арифметики// Квант. – 1972. - №6

• Гельфонд А.О. Решение уравнений в целых числах. – М.: Наука, 1978. – (Популярные лекции по математике).

• Михайлов И. О диофантовом анализе// Квант. – 1980. - №6

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

• https://ru.wikipedia.org/wiki/

11