Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например :

Число 12 делится на 1, на 2, на 3, на 4, на 6, на 12;

Число 36 делится на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.

Числа, на которые число делится нацело (для 12 это 1, 2, 3, 4, 6 и 12) называются делителями числа . Делитель натурального числа a - это такое натуральное число, которое делит данное число a без остатка. Натуральное число, которое имеет более двух делителей, называется составным . Обратите внимание, что числа 12 и 36 имеют общие делители. Это числа: 1, 2, 3, 4, 6, 12. Наибольший из делителей этих чисел - 12.

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

Кратко наибольший общий делитель чисел a и b записывают так:

Пример : НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример:

НОД (7; 9) = 1

Числа 7 и 9 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми чи слами .

Взаимно простые числа - это натуральные числа, которые имеют только один общий делитель - число 1. Их НОД равен 1.

Наибольший общий делитель (НОД), свойства.

• Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример : для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
• Следствие 1: множество общих делителей m и n совпадает с множеством делителей НОД(m , n ).
• Следствие 2: множество общих кратных m и n совпадает с множеством кратных НОК (m , n ).

Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.

• Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

и поэтому представим в виде линейной комбинации чисел m и n :

Это соотношение называется соотношением Безу , а коэффициенты u и v — коэффициентами Безу . Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a 1 , a 2 , … , a n ).

Вычисление наибольшего общего делителя (НОД).

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм . Кроме того, значение НОД (m ,n ) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m ,n ) и НОК (m ,n ) выражаются формулами:

Если чисел более двух: , их НОД находится по следующему алгоритму:

— это и есть искомый НОД.

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

Разберем пошагово вычисление наибольшего общего делителя:

1. Разложить делители чисел на простые множители:

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа - делитель. Далее в левом столбце записываем значения частных. Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

2. Подчёркиваем одинаковые простые множители в обоих числах:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Находим произведение одинаковых простых множителей и записываем ответ:

НОД (28; 64) = 2 . 2 = 4

Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».

Первый способ записи НОД:

Найти НОД 48 и 36.

НОД (48; 36) = 2 . 2 . 3 = 12

Второй способ записи НОД:

Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.

Д (10) = {1, 2, 5, 10}

Д (15) = {1, 3, 5, 15}

Д (10, 15) = {1, 5}

Решим задачу. У нас есть два типа печенья. Одни шоколадные, а другие простые. Шоколадных 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. Это число называют наибольшим общим делителем чисел 36 и 48.

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

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

• Наибольшее натуральное число, на которое делятся без остатка два числа a и b, называют наибольшим общим делителем этих чисел.

Иногда для сокращения записи используют аббревиатуру НОД.

Некоторые пары чисел имеют в качестве наибольшего общего делителя единицу. Такие числа называют взаимно простыми числами. Например, числа 24 и 35. Имеют НОД =1.

Как найти наибольший общий делитель

Для того чтобы найти наибольший общий делитель не обязательно выписывать все делители данных чисел.

Можно поступить иначе. Сначала разложить на простые множители оба числа.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

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

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

Останутся множители 2, 2 и 3. Их произведение равно 12. Это число и будет являться наибольшим общим делителем чисел 48 и 36.

Это правило можно распространить на случай с тремя, четырьмя и т.д. числами.

Общая схема нахождения наибольшего общего делителя

• 1. Разложить числа на простые множители.
• 2. Из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел.
• 3. Посчитать произведение оставшихся множителей.

Нахождение наиМЕНЬШЕГО общего кратного (НОК) и наиБОЛЬШЕГО общего делителя (НОД) натуральных чисел.

	2						5
	2						5
	3						3
	5

60=2*2*3*5
75=3*5*5
2) Выпишем множители, входящие в разложение первого из этих чисел и добавим к ним недостающий множитель 5 из разложения второго числа. Получаем: 2*2*3*5*5=300. Нашли НОК, т.е. эта сумма = 300. Не забываем размерность и пишем ответ:
Ответ: Мама дает по 300 рублей.

Определение НОД: Наибольшим общим делителем (НОД) натуральных чисел а и в называют наибольшее натуральное число c , на которое и a , и b делятся без остатка. Т.е. c это нибольшее натуральное число, для которого и а и б являются кратными.

Памятка: Существуют два подхода к определению натуральных чисел

• числа, используемые при: перечислении (нумеровании) предметов (первый, второй, третий, …); - в школах, обычно так .
• обозначении количества предметов (нет покемонов - ноль, один покемон, два покемона, …).

Отрицательные и нецелые (рациональные, вещественные, …) числа натуральными не являются. Ноль некоторые авторы включают в множество натуральных чисел, другие - нет. Множество всех натуральных чисел принято обозначать символом N

Памятка: Делителем натурального числа a называют число b, на которое a делится без остатка. Кратным натуральному числу b называют натуральное число a , которое делится на b без остатка. Если число b - делитель числа a , то a кратно числу b . Пример: 2 - делитель 4, а 4 кратно двум. 3 - делитель 12, а 12 кратно 3.
Памятка: Натуральные числа называют простыми, если они делятся без остатка только на себя и на 1. Взаимно простыми называются числа у которых только один общий делитель, равный 1.

Определение как найти НОД в общем случае: Чтобы найти НОД (Наибольший общий делитель) нескольких натуральных чисел надо:
1) Разложить их на простые множители. (Для этого Вам может очень пригодиться Таблица простых чисел.)
2) Выписать множители, входящие в разложение одного из них.
3) Вычеркнуть те, которые не входят в разложение остальных чисел.
4) Перемножить множители, получившиеся в п.3).

Задача 2 на (НОК): К новому году Коля Пузатов купил в городе 48 хомяков и 36 кофейников. Фекла Дормидонтова, как самая честная девочка класса, получила задание разделить это имущество на наибольшее возможное число подарочных наборов для учителей. Какое число наборов получилось? Какой состав наборов?

Пример 2.1. решения задачи на нахождение НОД. Нахождение НОД подбором.
Решение: Каждое из чисел и 48, и 36 должно делиться на число подарков.
1) Выпишем делители 48: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) Выпишем делители 36: 36, 18, 12 , 9, 6, 3, 2, 1 Выбираем наибольший общий делитель. Оп-ля-ля! Нашли, это число наборов 12 штук.
3) Поделим 48 на 12 получим 4, поделим 36 на 12, получим 3. Не забываем размерность и пишем ответ:
Ответ: Получится 12 наборов по 4 хомяка и 3 кофейника в каждом наборе.

Наименьшее общее кратное двух чисел непосредственно связано с наибольшим общим делителем этих чисел. Эта связь между НОД и НОК определяется следующей теоремой.

Теорема.

Наименьшее общее кратное двух положительных целых чисел a и b равно произведению чисел a и b , деленному на наибольший общий делитель чисел a и b , то есть, НОК(a, b)=a·b:НОД(a, b) .

Доказательство.

Пусть М – какое-нибудь кратное чисел a и b . То есть, М делится на a , и по определению делимости существует некоторое целое число k такое, что справедливо равенство M=a·k . Но М делится и на b , тогда a·k делится на b .

Обозначим НОД(a, b) как d . Тогда можно записать равенства a=a 1 ·d и b=b 1 ·d , причем a 1 =a:d и b 1 =b:d будут взаимно простыми числами . Следовательно, полученное в предыдущем абзаце условие, что a·k делится на b , можно переформулировать так: a 1 ·d·k делится на b 1 ·d , а это в силу свойств делимости эквивалентно условию, что a 1 ·k делится на b 1 .

Также нужно записать два важных следствия из рассмотренной теоремы.

Общие кратные двух чисел совпадают с кратными их наименьшего общего кратного.

Это действительно так, так как любое общее кратное M чисел a и b определяется равенством M=НОК(a, b)·t при некотором целом значении t .

Наименьшее общее кратное взаимно простых положительных чисел a и b равно их произведению.

Обоснование этого факта достаточно очевидно. Так как a и b взаимно простые, то НОД(a, b)=1 , следовательно, НОК(a, b)=a·b:НОД(a, b)=a·b:1=a·b .

Наименьшее общее кратное трех и большего количества чисел

Нахождение наименьшего общего кратного трех и большего количества чисел можно свести к последовательному нахождению НОК двух чисел. Как это делается, указано в следующей теореме.a 1 , a 2 , …, a k совпадают с общими кратными чисел m k-1 и a k , следовательно, совпадают с кратными числа m k . А так как наименьшим положительным кратным числа m k является само число m k , то наименьшим общим кратным чисел a 1 , a 2 , …, a k является m k .

Список литературы.

• Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
• Виноградов И.М. Основы теории чисел.
• Михелович Ш.Х. Теория чисел.
• Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.

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

Навигация по странице.

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

Заметим, что если бы мы с самого начала обратились к таблице простых чисел , то выяснили бы, что числа 661 и 113 – простые, откуда можно было бы сразу сказать, что их наибольший общий делитель равен 1 .

Ответ:

НОД(661, 113)=1 .

Нахождение НОД с помощью разложения чисел на простые множители

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители . Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители .

Приведем пример для пояснения правила нахождения НОД. Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5 . Общими простыми множителями, участвующими в разложении чисел 220 и 600 , являются 2 , 2 и 5 . Следовательно, НОД(220, 600)=2·2·5=20 .

Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то этим будет найден наибольший общий делитель чисел a и b .

Рассмотрим пример нахождения НОД по озвученному правилу.

Пример.

Найдите наибольший общий делитель чисел 72 и 96 .

Решение.

Разложим на простые множители числа 72 и 96 :

То есть, 72=2·2·2·3·3 и 96=2·2·2·2·2·3 . Общими простыми множителями являются 2 , 2 , 2 и 3 . Таким образом, НОД(72, 96)=2·2·2·3=24 .

Ответ:

НОД(72, 96)=24 .

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что НОД(m·a 1 , m·b 1)=m·НОД(a 1 , b 1) , где m – любое целое положительное число.

Нахождение НОД трех и большего количества чисел

Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a 1 , a 2 , …, a k равен числу d k , которое находится при последовательном вычислении НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k-1 , a k)=d k .

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

Пример.

Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .

Решение.

В этом примере a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 .

Сначала по алгоритму Евклида определим наибольший общий делитель d 2 двух первых чисел 78 и 294 . При делении получаем равенства 294=78·3+60 ; 78=60·1+18 ; 60=18·3+6 и 18=6·3 . Таким образом, d 2 =НОД(78, 294)=6 .

Теперь вычислим d 3 =НОД(d 2 , a 3)=НОД(6, 570) . Опять применим алгоритм Евклида: 570=6·95 , следовательно, d 3 =НОД(6, 570)=6 .

Осталось вычислить d 4 =НОД(d 3 , a 4)=НОД(6, 36) . Так как 36 делится на 6 , то d 4 =НОД(6, 36)=6 .

Таким образом, наибольший общий делитель четырех данных чисел равен d 4 =6 , то есть, НОД(78, 294, 570, 36)=6 .

Ответ:

НОД(78, 294, 570, 36)=6 .

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

Пример.

Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.

Решение.

Разложим числа 78 , 294 , 570 и 36 на простые множители, получаем 78=2·3·13 , 294=2·3·7·7 , 570=2·3·5·19 , 36=2·2·3·3 . Общими простыми множителями всех данных четырех чисел являются числа 2 и 3 . Следовательно, НОД(78, 294, 570, 36)=2·3=6 .