Алгоритм Евклида - нахождение наибольшего общего делителя

Алгоритм Евклида - нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

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

Алгоритм нахождения НОД делением

1. Большее число делим на меньшее.

2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).

3. Если есть остаток, то большее число заменяем на остаток от деления.

4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

Алгоритм нахождения НОД вычитанием

1. Из большего числа вычитаем меньшее.

2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).

3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

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

Алгоритм Евклида заключается в следующем: если большее из двух чисел делится на меньшее — наименьшее число и будет их наибольшим общим делителем. Использовать метод Евклида можно легко по формуле нахождения наибольшего общего делителя.

Формула НОД: НОД (a, b) = НОД (b, с), где с — остаток от деления a на b.

Пример 1. Найти НОД для 24 и 8.

Как рассуждаем:

Так как 24 делится на 8 и 8 тоже делится на 8, значит, 8 — общий делитель этих чисел. Этот делитель является наибольшим, потому что 8 не может делиться ни на какое число, большее его самого. Поэтому: НОД (24, 8) = 8.

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

Большее число поделить на меньшее.

Меньшее число поделить на остаток, который получается после деления.

Первый остаток поделить на второй остаток.

Второй остаток поделить на третий и т. д.

Деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель и есть наибольший общий делитель.

Пример 2. Найти наибольший общий делитель чисел 140 и 96:

Как решаем:

140 : 96 = 1 (остаток 44)

96 : 44 = 2 (остаток 8)

44 : 8 = 5 (остаток 4)

8 : 4 = 2

Последний делитель равен 4 — это значит: НОД (140, 96) = 4.

Ответ: НОД (140, 96) = 4

Пошаговое деление можно записать столбиком:

Чтобы найти наибольший общий делитель трех и более чисел, делаем в такой последовательности:

1. Найти наибольший общий делитель любых двух чисел из данных.

2. Найти НОД найденного делителя и третьего числа.

3. Найти НОД последнего найденного делителя и четвёртого числа и т. д.

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

Найдем  .

Идея алгоритма в следующем: заменяем большее из чисел их разностью.

 при этом НОД не меняется.

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

Продолжим

Можно продолжать и дальше, но тут ответ уже очевиден

, т.к.  .

Ответ  11.

Мы можем использовать этот алгоритм и для тех чисел, которые мы уже разобрали.

, т.к. 

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

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

Заключение

Сегодня мы с вами познакомились с новым понятием - наибольший общий делитель, определили его, обсудили его свойства и рассмотрели несколько способов вычисления НОД. Первый – выписать делители и найти из них наибольший. Второй – разложить на множители и выбрать сомножитель, являющийся общим, этот способ, как мы помним, работает для трех и более чисел. И третье – алгоритм Евклида. Когда мы буде говорить о дробях, о сложении дробей с разными знаменателями, идея НОД нам очень понадобится. На этом наш урок закончен.

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

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

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

Рассматриваемые на занятиях кружка вопросы выходят за базисный уровень обязательных знаний по математике, но при этом они тесно примыкают к вопросам программного материала.

В этой статье предлагается разработка занятия кружка по теме «Алгоритм Евклида».

Введение.

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

Когда мы готовим чай, то пользуемся определенным алгоритмом (иногда заданным инструкцией, напечатанной на упаковке). Когда берем книги в библиотеке, мы следуем определенным правилам пользования библиотечными книгами, т.е. выполняем определенный алгоритм.

Разве можно перечислить все задачи, при решении которых мы используем определенные алгоритмы?

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

Термин «алгоритм» произошел от имени ученого VIII–IX веков Аль -Хорезми. Его имя говорит о том, что он родился в городе Хорезми, который сейчас входит в состав Узбекистана. Большую часть своей жизни Аль

-Хорезми провел при дворе багдадских халифов. Из математических работ Аль-Хорезми до нас дошли всего две алгебраическая и арифметическая. От названия первой книги родилось слово «алгебра».

Первые строки второй книги были переведены так: «Сказал Алгоритми. Воздадим хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово «алгоритм».

Исследуем известный в математике «алгоритм Евклида».

1. Алгоритм Евклида. Вспомним, как можно найти наибольший общий делитель (НОД) двух натуральных чисел: достаточно выписать разложения этих чисел на простые множители и взять их общую часть. Однако для больших чисел эта процедура практически неосуществима. Попробуйте, например, таким способом найти НОД чисел 1381 955 и 690713. К счастью, существует другой способ, позволяющий вычислить наибольший

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

Покажем, как работает алгоритм Евклида на конкретных примерах.

Пример 1

.

Найти НОД(32, 12) с помощью алгоритма Евклида.

Решение.

НОД(32, 12) = НОД(32–12, 12) = НОД(20, 12) = НОД(20–12, 12) = НОД(8, 12)= НОД(8, 12–8) = НОД(8, 4) = НОД(8–4, 4) = НОД(4, 4)= 4.

Пример 2

Найти НОД(451, 287) с помощью алгоритма Евклида.

Решение.

НОД(451, 287) = НОД(287, 164) = НОД(164, 123) = НОД(123, 41) = НОД(82, 41) = = НОД(41, 41) = 41.

Приведенный способ вычисления не является оптимальным. Например, для нахождения НОД(100, 2) следует выполнить 50 операций вычитания.

Б) Ускорить процесс нахождения наибольшего общего делителя позволит следующее соображение: когда несколько раз вычитаем из большего числа меньшее (А–В, А–2В, А–3В), то остановимся мы тогда, когда число из большего станет меньшим, например, так: А–4В

остаток от деления А на В. Так что можно было не расписывать все А–В, А–2В и так далее, а сразу заменить

А на остаток от деления А на В. Часто это оказывается быстрее, чем много раз вычитать [4].

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

Пусть А = ВQ+ R, тогда НОД(А, В) = НОД(В, R)[5]