Карточки
Тесты
Зави
Наибольший общий делитель
Наибольший общий делитель
В уроке про разложение на простые множители вы дробили число на простые множители. Теперь научимся находить наибольший общий делитель двух чисел — НОД: сначала перебором делителей, затем по разложению. Разберем, почему НОД не бывает больше меньшего из чисел, и познакомимся с взаимно простыми числами.
Вопрос, к которому мы вернемся во втором разделе: прямоугольник $12\times 18$ клеток надо выложить одинаковыми квадратными плитками без обрезков. Какую наибольшую плитку можно взять?
Делитель, который подходит обоим числам
Выпишем делители числа $12$: $1$, $2$, $3$, $4$, $6$, $12$. Теперь делители числа $18$: $1$, $2$, $3$, $6$, $9$, $18$. Некоторые числа встречаются в обоих списках: $1$, $2$, $3$, $6$. На каждое из них делятся и $12$, и $18$.
Число $4$ делит $12$, но не делит $18$: $18:4$ — это $4$ и остаток $2$. Число $9$ делит $18$, но не делит $12$. Такие делители подходят только одному числу.
Определение
Общий делитель чисел $a$ и $b$ — число, на которое без остатка делится и $a$, и $b$.
Число $1$ — общий делитель любых двух натуральных чисел: на $1$ делится каждое число. Поэтому общий делитель у двух чисел есть всегда, вопрос лишь в том, есть ли другие.
Самая крупная плитка без обрезков
Вернемся к прямоугольнику $12\times 18$. Как и в уроке про простые и составные числа, представим число клетками: одна сторона — $12$ клеток, другая — $18$. Возьмем квадратную плитку со стороной $s$ клеток. Чтобы она легла ровными рядами без обрезков, вдоль стороны $12$ должно уложиться целое число плиток, и вдоль стороны $18$ — тоже. Значит, $s$ делит и $12$, и $18$: сторона плитки — общий делитель.
Проверим плитку со стороной $4$. Вдоль стороны $12$ ложатся ровно $3$ плитки, а вдоль стороны $18$ — только $4$ плитки, и остается полоса шириной $2$ клетки. Ее пришлось бы резать. Число $4$ не делит $18$ — и плитка не подходит.
Подходят плитки $1$, $2$, $3$ и $6$. Заметьте: все они — делители самой крупной, $6$. Так бывает всегда: общие делители двух чисел — это делители их НОД. Самая крупная — со стороной $6$: прямоугольник выкладывается всего шестью плитками, по $2$ в ряд вдоль стороны $12$ и по $3$ — вдоль стороны $18$. Это и есть ответ на вопрос из начала урока. Крупнее плитки нет: следующий кандидат должен был бы делить $12$, а все делители $12$, большие $6$, — это только $12$, но $12$ не делит $18$.
Определение
Наибольший общий делитель чисел $a$ и $b$ — наибольшее натуральное число, на которое без остатка делятся и $a$, и $b$. Обозначение: $\text{НОД}(a;\,b)$.
На модели: $\text{НОД}(a;\,b)$ — сторона самой крупной квадратной плитки, которой прямоугольник $a\times b$ выкладывается без обрезков.
Первый способ: перебрать делители
Плитки удобно перебирать на маленьких числах. Для больших чисел действуем так же, но без рисунка: выписываем делители и ищем наибольший общий.
Правило
Чтобы найти $\text{НОД}(a;\,b)$ перебором:
- выпишите все делители меньшего числа по убыванию;
- проверяйте их по очереди: делится ли на них большее число;
- первый подходящий делитель и есть НОД.
Почему начинаем с меньшего числа? НОД делит меньшее число, а делитель числа не больше самого числа. Значит, НОД не больше меньшего из двух чисел, и искать его надо среди делителей меньшего. А идем от крупных делителей к мелким, чтобы первый же подходящий оказался наибольшим.
Пример 1
Найдите $\text{НОД}(24;\,36)$.
Шаг 1. Делители меньшего числа $24$ по убыванию: $24$, $12$, $8$, $6$, $4$, $3$, $2$, $1$.
Шаг 2. $36:24$ — с остатком $12$, не подходит. $36:12=3$ — подходит.
Шаг 3. Первый подходящий делитель — $12$.
Проверка на модели. Прямоугольник $24\times 36$ выкладывается плитками $12\times 12$: по $2$ в ряд и по $3$ в столбец, всего $6$ плиток.
Ответ: $\text{НОД}(24;\,36)=12$.
Второй способ: общие простые множители
Перебор долгий, если у чисел много делителей. Тогда помогает разложение. Возьмем $36$ и $60$:
Делитель числа $36$ собирается только из его множителей: двойка не больше двух раз, тройка не больше двух раз. Делитель $60$ — двойка не больше двух раз, тройка не больше одного раза, пятерка не больше одного раза. Общий делитель обязан уложиться в оба ограничения сразу.
Двойку можно взять дважды — так разрешают оба числа. Тройку — только один раз: больше не позволяет $60$. Пятерку взять нельзя: в $36$ ее нет. Получаем $2^2\cdot 3=12$.
На модели: плитка со стороной $2\cdot 2\cdot 3=12$ укладывается и в сторону $36$ ($3$ раза), и в сторону $60$ ($5$ раз). Добавим еще одну тройку — сторона $36$ уже не уложится в $60$: в $60$ тройка только одна.
Правило
Чтобы найти $\text{НОД}(a;\,b)$ по разложению:
- разложите каждое число на простые множители;
- из полученных разложений выберите общие простые множители, каждый — в наименьшей из двух степеней;
- перемножьте выбранные общие множители;
- проверьте, что оба числа делятся на полученное произведение.
Пример 2
Найдите $\text{НОД}(84;\,126)$.
Шаг 1. Разложим: $84=2^2\cdot 3\cdot 7$, $126=2\cdot 3^2\cdot 7$.
Шаг 2. Общие множители $2$, $3$, $7$. Двойка: степени $2$ и $1$, берем $1$. Тройка: степени $1$ и $2$, берем $1$. Семерка: степени $1$ и $1$, берем $1$.
Шаг 3. $2\cdot 3\cdot 7=42$.
Шаг 4. Проверка: $84:42=2$, $126:42=3$.
Ответ: $\text{НОД}(84;\,126)=42$.
Почему НОД не равен меньшему числу
Две ошибки встречаются чаще других. Первая: «НОД — это меньшее из двух чисел». Вторая: из разложений берут общие множители, но в большей степени, а не в меньшей. Для чисел $36$ и $60$ обе ошибки дают один и тот же неверный ответ.
Ошибка
Как ошибаются. Иксератопс пишет: $\text{НОД}(36;\,60)=36$. Он рассуждает так: у чисел общие множители $2$ и $3$, берем $2^2$ и $3^2$, получается $36$; к тому же $36$ — меньшее число.
Проверка на числах. Делится ли $60$ на $36$? $60:36$ — это $1$ и остаток $24$. Значит, $36$ вообще не делитель $60$, тем более не наибольший общий. На модели: плитка $36\times 36$ ложится вдоль стороны $36$, но вдоль стороны $60$ после одной плитки остается полоса шириной $24$.
Где сломалось рассуждение. Тройку взяли во второй степени, а в числе $60$ она только в первой. Множитель общего делителя должен поместиться в оба числа, поэтому берем наименьшую степень: $2^2\cdot 3=12$.
Меньшее число бывает НОДом, но только в одном случае: если большее число делится на меньшее. Об этом — в следующем разделе.
Особые случаи: НОД равен 1, меньшему числу, НОД трех чисел
Возьмем прямоугольник $8\times 15$. Делители $8$: $1$, $2$, $4$, $8$. Делители $15$: $1$, $3$, $5$, $15$. Общий только $1$, и выложить прямоугольник без обрезков можно лишь единичными клетками. При этом ни $8$, ни $15$ не простое число.
Определение
Взаимно простые числа — натуральные числа, у которых наибольший общий делитель равен $1$.
Обратите внимание
Взаимно простыми бывают и составные числа, как $8$ и $15$. Это свойство пары чисел, а не каждого числа по отдельности. Проверять его нужно поиском общего делителя, а не проверкой, простое ли каждое число.
Другой крайний случай — прямоугольник $12\times 48$. Плитка $12\times 12$ закрывает сторону $12$ целиком, а вдоль стороны $48$ ложится ровно $4$ раза: $48=12\cdot 4$. Крупнее плитку не взять — она не поместится в сторону $12$. Значит, $\text{НОД}(12;\,48)=12$.
Правило
Если большее число делится на меньшее, то НОД равен меньшему числу:
НОД трех чисел находят по цепочке: сначала НОД двух, затем НОД результата и третьего числа.
Пример 3
Найдите $\text{НОД}(18;\,24;\,30)$.
Шаг 1. $\text{НОД}(18;\,24)=6$.
Шаг 2. $\text{НОД}(6;\,30)=6$.
Шаг 3. Проверка: $18:6=3$, $24:6=4$, $30:6=5$.
Ответ: $6$.
Вывод
НОД понадобится при сокращении дробей и в задачах, где что-то делят на равные части без остатка. Главное помнить через модель: НОД — сторона самой крупной квадратной плитки, которая укладывается в обе стороны прямоугольника без обрезков. В следующем уроке разберем наименьшее общее кратное — оно отвечает на другой вопрос.
Часто задаваемые вопросы
Нет. НОД делит каждое из чисел, а делитель числа не больше самого числа. Поэтому НОД не больше меньшего из двух чисел. Если у вас получилось больше — проверьте, не взяли ли вы наибольшие степени множителей.
Если меньшее число небольшое и у него мало делителей, быстрее перебор. Если числа большие или у них много делителей, надежнее разложение. Ответ в обоих случаях один, поэтому одним способом можно проверить другой.
Да, если это разные простые числа: у каждого делители только 1 и оно само, общий — только 1. Но взаимно простыми бывают и составные числа, например 8 и 15.
НОД и есть произведение общих простых множителей, но каждый берется в наименьшей степени. Если взять множитель в большей степени, получится число, на которое одно из чисел не делится.
Следующий урок
НОД отвечает на вопрос «какая самая крупная общая часть?». Другой вопрос — «когда события совпадут?» — решает наименьшее общее кратное.
Повторите
- Разложение на простые множители нужно для поиска НОД: урок про разложение на простые множители.
- Простое число имеет ровно два делителя, составное — больше двух: урок про простые и составные числа.
Тренажер темы
Закрепите тему на задачах: тренажер «НОД двух чисел» и тренажер «НОД и взаимно простые числа».
5
5
1
5