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

Лабораторная работа 6. Алгоритм Евклида и его применение

Теория:

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

1. Нахождения НОД и НОК по алгоритму Евклида методом деления:

Как известно, деление с остатком целых чисел a - делимое и b - делитель, где b ≠ 0, подразумевает нахождение таких целых чисел q и r, что выполняется равенство:

a = b ∙ q + r, где

q - называется неполным частным,

r - остаток от деления, который не может быть отрицательным числом и по модулю не может быть больше делителя.

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

Приведем примеры:

Найдем НОД (36; 30), для этого сначала найдем остаток от деления 36 на 30

36 : 30 = 1 (остаток 6), так как 36 = 30 ∙ 1 + 6, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 30 на 6

30 : 6 = 5 (остаток 0) так как 30 = 6 ∙ 5 + 0, остаток от деления равен нулю, значит НОД равен предыдущему остатку от деление 6

Ответ: НОД (36; 30) = 6

Чтобы найти наименьшее общее кратное НОК чисел a и b необходимо произведение a и b разделить на НОД (a; b).  НОК (36; 30) = (36 ∙ 30) : 6 = 180

Найдем НОД  (7512; 2991), для этого сначала найдем остаток от деления 7512 на 2991

Решение:

(Шаг 1) 7512 : 2991 = 2 (остаток 1530), так как 7512 = 2991 ∙ 2 + 1530, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 2991 на 1530

(Шаг 2) 2991 : 1530 = 1 (остаток 1461), так как 2991 = 1530 ∙ 1 + 1461, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 1530 на 1461

(Шаг 3) 1530 : 1461 = 1 (остаток 69), так как 1530 = 1461 ∙ 1 + 69, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 1461 на 69

(Шаг 4) 1461 : 69 = 21 (остаток 12), так как 1461 = 69 ∙ 21 + 12, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 69 на 12

(Шаг 5) 69 : 12 = 5 (остаток 9), так как 69 = 12 ∙ 5 + 9, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 12 на 9

(Шаг 6) 12 : 9 = 1 (остаток 3), так как 12 = 9 ∙ 1 + 3, остаток от деления не равен нулю, поэтому продолжаем деление, разделим 9 на 3

9 : 3 = 3 (остаток 0), так как 9 = 3 ∙ 3 + 0, равен нулю, значит НОД равен предыдущему остатку от деления

Ответ: НОД (7512; 2991) = 3        

Чтобы найти НОК чисел a и b необходимо произведение a и b разделить на НОД (a ;b)

НОК (7512; 2991) = (7512 ∙ 2991) : 3 = 7489464

1. Дополнительно: https://www.youtube.com/watch?v=yrOKPlg1TXg 

https://www.youtube.com/watch?v=TRyUEmjjoTs

1. Задание для самостоятельной работы

1. С помощью алгоритма Евклида найти НОД чисел 9991 и 3977.
2. Найти НОД чисел a = 2151, b = 1935.
3. Найти НОД чисел 140 и 96.
4. С помощью алгоритма Евклида разложить рациональное число 78/14 в конечную цепную дробь.

1. Реализовать программный код нахождения НОД по алгоритму Евклида (на языке программирования Python или C#).

1. Вопросы для самоконтроля

1. Что представляет собой последовательность неполных частных и как её найти?
2. Сформулируйте определение подходящей дроби.
3. Как с помощью алгоритма Евклида определить наибольший общий делитель двух натуральных чисел?
4. Какова связь между алгоритмом Евклида и разложением рационального числа в конечную цепную дробь?
5. Как с помощью алгоритма Евклида решить сравнение первой степени?