Общим делителем нескольких чисел называется число, которое является делителем для каждого из них.
Пример: Числа 12 и 18 имеют общий делитель 3, так как 3 является делителем и числа 12 (12÷3=4 – делится без остатка), и числа 18 (18÷3=6 делится без остатка). Число 2 также общий делитель чисел 12 и 18 (12÷2=6, 18÷2=9).
Среди всех общих делителей всегда имеется наибольший.
Наибольшим общим делителем нескольких чисел называется самое большое число, на которое делятся все эти числа.
Для краткой записи наибольшего общего делителя используют аббревиатуру НОД. Для двух чисел a и b наибольший общий делитель обозначают как НОД(a,b), для трех чисел a, b и c – НОД(a,b,c) и так далее.
Пример: Числа 5 и 15 имеют наибольший общий делитель 5, то есть НОД(5,15)=5. Так как число 5 делится на 1, на 5; число 15 делится на 1, на 3, на 5, на 15, то числа 5 и 15 имеют общие делители 1 и 5, где наибольший – 5.
Пример: Числа 7 и 11 имеют наибольший общий делитель 1, так как число 7 делится на 1, на 7; число 11 делится на 1, на 11, где общий делитель 1 – наибольший, то есть НОД(7,11)=1.
Два числа, наибольший общий делитель которых равен 1, называются взаимно простыми.
Для нахождения наибольшего общего делителя на практике, как правило, используется три способа.
- Первый способ заключается в поиске всех возможных делителей данных чисел и в выборе наибольшего из них (обычно применяется, когда числа небольшие).
Пример: Найдем наибольший общий делитель чисел 8 и 12. Для числа 8 делителями являются числа 1, 2, 4, 8. Для числа 12 делителями являются числа 1, 2, 3, 4, 6, 12. В выписанных делителях определяем общий и наибольший – это число 4. Таким образом, НОД(8,12)=4.
- Второй способ – нахождение НОД с помощью разложения чисел на простые множители.
Чтобы найти наибольший общий делитель нескольких чисел, достаточно, разложив их на простые множители, перемножить те из этих множителей, которые являются общими для всех данных чисел.
Пример: Найдем наибольший общий делитель чисел 36 и 96. Разложим на простые множители числа 36 и 96 (алгоритм разложения на простые множители был рассмотрен в статье: Конспект № 15. Тема: «Разложение чисел на простые множители»).
Выделим общие множители (отмечены красным и зеленым цветами).
Итак, общими простыми множителями чисел 36 и 96 являются числа 2, 2, 3 – перемножив их, найдем НОД. Таким образом, НОД(36,96)=2×2×3=12.
- Третий способ – нахождение НОД посредством последовательного деления (называют способом Евклида).
Чтобы найти наибольший общий делитель двух чисел, делим большее из них на меньшее, затем меньшее на первый остаток, затем первый остаток на второй, второй на третий и так далее до тех пор, пока не получится в остатке ноль; тогда последний делитель будет наибольшим общим делителем данных чисел.
Пример: Найдем наибольший общий делитель чисел 195 и 78. Делим большее из данных чисел на меньшее: 195÷78 – получаем 2 в остатке 39. Далее делим меньшее из данных чисел на остаток 39, получаем 78÷39=2 (без остатка). То есть последний делитель 39 – искомый НОД. Последовательное деление удобнее записывать столбиком.
Таким образом, НОД(195, 78)=39.
Чтобы найти способом последовательного деления наибольший общий делитель трех или более чисел, находим сначала наибольший общий делитель каких-нибудь двух из них, затем – наибольший общий делитель найденного делителя и третьего данного числа, далее – наибольший общий делитель последнего делителя и четвертого данного числа и так далее.
Пример: Найдем наибольший общий делитель трех чисел 12, 16 и 36. Определим сначала наибольший общий делитель чисел 12 и 16.
Получили НОД(12, 16)=4. Далее найдем наибольший общий делитель найденного делителя 4 и третьего данного числа 36.
Таким образом, НОД(12, 16, 36)=4.
Предыдущая статья: Конспект № 15. Тема: «Разложение чисел на простые множители».