Классы
Предметы

Наибольший общий делитель. Алгоритм Евклида

Этот видеоурок доступен по абонементу
Подробнее об абонементе, платных и бесплатных уроках

У вас уже есть абонемент? Войти

Оплатить абонементот 75 руб. в месяц
У вас уже есть абонемент? Войти
Наибольший общий делитель. Алгоритм Евклида

Найти наибольший общий делитель двух чисел можно разными способами. Некоторые из них были рассмотрены ранее. Этот урок посвящен еще одному алгоритму нахождения НОД – алгоритму Евклида. Он рассматривается в двух вариантах: с вычитанием и с делением. Рассмотренные примеры дают возможность разобрать и закрепить новый материал.

Если у вас возникнет сложность в понимании тему, рекомендуем посмотреть урок «Число как объект изучения (Теория чисел)»

Введение

Давайте разберемся, что означает понятие «наибольший общий делитель».

Попробуем объяснить в не строгой форме.

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

Сейчас рассмотрим пример, который иллюстрирует данную идею:

Задача 1

У нас есть 48 шоколадок, и 36 конфет. Мы хотим из этого набора составить некоторые комплекты, которые мы подарим детям на Новый Год. Какое наибольшее количество комплектов мы можем сделать так, чтобы всем детям досталось поровну?

Решение:

Чтобы поделить шоколадки и конфеты поровну нам нужно разделить и шоколадки и кофеты нацело на количество подарков. Например, если поделить их на два подарка, то в каждом подарке будет по 24 шоколадки, и 18 конфет. То есть количество шоколадок или конфет нужно поделить на количество подарков, и оно будет делителем количества шоколадок или конфет.

Давайте найдем наибольший общий делитель чисел 48 и 36.

Выпишем все делители для обоих чисел:48:

  • 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
  • 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

 Давайте выделим из них общие делители:

 

  • 1, 2, 3, 4, 6, 12

 Наибольший из общих делителей – 12.

Значит, мы можем сделать 12 подарков, и не сложно посчитать, что в каждом из них будет по 4 шоколадки, и по 3 конфеты.

Ответ: 12 комплектов.

Давайте дадим точное определение наибольшему общему делителю.

Определение наибольшего общего делителя

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

Есть два числа ,  их наибольший делитель будет записан так:

.

Например, .

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

Существует еще такая форма записи НОД:

Но чаще используют первый вариант.

Свойства НОД

Давайте подумаем в каких границах может находиться НОД двух чисел.

Первое свойство.

У любых двух чисел есть хотя бы один общий делитель, и это число 1.

И здесь мы введем понятие взаимно простых чисел.

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

Что это значит? Это значит, что на самом деле у них нет других общих делителей, кроме единицы. Какие примеры взаимно простых чисел мы можем привести?

Например, числа 2 и 3, которые мы рассматривали выше. Числа 3 и 7 также взаимно простые.

Очень важно не путать понятия взаимно простых чисел, и простых чисел.

Из того что числа взаимно простые еще не следует, что они простые.

Например, . Тем не менее ни 9, ни 10 не являются простыми числами, но они взаимно простые.

Второе свойство.

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

 – такое наибольшее число, на которое делятся и , и . Логично, что наибольшее число, на которое делится  – , а  – по условию.

Значит, .

Например, ;

Аналогично ;

, потому что  и больше 1 результат быть не может.

Теперь давайте найдем удобный способ нахождения НОД.

Задача 2

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

Рассмотрим все те же числа 36 и 48:

  •  – это т.н. «каноническое разложение» числа 36;

Давайте выделим общие множители столько раз, сколько они встречаются в результате разложения каждого числа: 2 ,2 ,3.

При перемножении этих чисел мы и получим НОД.

Ответ: 12.

Давайте рассмотрим другой пример.

Задача 3

Возьмем числа 25 и 40. Найдем НОД.

;

Ответ: 5.

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

Давайте попробуем на примере.

Задача 4

 

Найти .

Ответ: 4;

Итак, мы с вами научились вычислять НОД двух чисел и трех чисел.

Давайте теперь рассмотрим еще несколько свойств НОД.

Свойства НОД (продолжение)

  • ;

Вспомним, что такое простые числа. Простое число – это число, которое имеет ровно два натуральных делителя – единицу и себя.

  • ; ,  – различные простые числа, следовательно эти числа – взаимно простые;
  • ; т.е. последовательные числа также взаимно простые

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

Если взять числа больше, например, 143 и 257, разложение на множители уже не так очевидно, как в случае с 16 и 36, поэтому нужно найти универсальный метод, который бы работал для любых чисел, даже если разложение на множители затруднено. И такой универсальный метод есть. Он называется алгоритм Евклида. Этому алгоритму уже более двух тысяч лет, и тем не менее он радует глаз математиков и по сей день.

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

Найдем .

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

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

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

Продолжим

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

, т.к. .

Ответ 11.

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

, т.к.

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

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

Заключение

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

 

Список рекомендованной литературы

1. Виленкин Н.Я., Жохов В.И., Чесноков А.С., Шварцбурд С.И. Математика 6. – М.: Мнемозина, 2012.

2.      Мерзляк А.Г., Полонский В.В., Якир М.С. Математика 6 класс. – Гимназия. 2006.

3. Депман И.Я., Виленкин Н.Я. За страницами учебника математики. – М.: Просвещение, 1989.

4. Рурукин А.Н., Чайковский И.В. Задания по курсу математика 5–6 класс. – М.: ЗШ МИФИ, 2011.

5. Рурукин А.Н., Сочилов С.В., Чайковский К.Г. Математика 5–6. Пособие для учащихся 6-х классов заочной школы МИФИ. – М.: ЗШ МИФИ, 2011.

6. Шеврин Л.Н., Гейн А.Г., Коряков И.О., Волков М.В. Математика: Учебник-собеседник для 5–6 классов средней школы. – М.: Просвещение, Библиотека учителя математики, 1989.

 

Рекомендованные ссылки на интернет ресурсы

Интернет портал «CleverStudents» (Источник)

Интернет портал «Фестиваль педагогических идей» (Источник)

Интернет портал «База презентаций» (Источник)

 

Рекомендованное домашнее задание

Найдите НОД чисел: 27, 15 и 9.

Найдите НОД (424;477) при помощи алгоритма Евклида.

Туристы проехали за первый день 56 км, а за второй – 72 км, причем их скорость была одинаковой и выражалась целым числом км/ч, и каждый день они были в пути целое число часов. Найдите скорость, с которой ехали туристы, если она была наибольшей из удовлетворяющих условию задачи.