Введение
Давайте разберемся, что означает понятие «наибольший общий делитель».
Попробуем объяснить в не строгой форме.
Допустим у нас есть два числа, у этих двух чисел есть число, на которое они оба делятся. Максимально большое такое число и есть наибольшим общим делителем. Т.е. наибольший общий делитель – наибольшее число, на которое можно разделить несколько чисел без остатка. Строгое определение мы рассмотрим чуть позже.
Сейчас рассмотрим пример, который иллюстрирует данную идею:
Задача 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 км, причем их скорость была одинаковой и выражалась целым числом км/ч, и каждый день они были в пути целое число часов. Найдите скорость, с которой ехали туристы, если она была наибольшей из удовлетворяющих условию задачи.
