Что такое наибольший общий делитель: определение термина
Наибольшим общим делителем называют общий делитель чисел, который больше всех остальных общих делителей. Например, у чисел 12 и 18 общие делители — 1, 2, 3, 6, и самый большой из них равен 6, значит НОД(12, 18) = 6.
НОД используют, чтобы сокращать дроби, находить общие части, упрощать выражения и решать задачи на делимость. Если НОД равен 1, числа называют взаимно простыми.
Как находят наибольший общий делитель
Один способ — разложить каждое число на простые множители и взять общие множители в минимальных степенях. Например, 12 = 2²·3, 18 = 2·3². Общие множители: 2 и 3, значит НОД равен 2·3 = 6.
Более быстрый способ — алгоритм Евклида. Он основан на том, что НОД двух чисел не меняется, если большее число заменить остатком от деления на меньшее. Например, для 48 и 18: 48 делится на 18 с остатком 12, значит НОД(48, 18) = НОД(18, 12).
Дальше: 18 делится на 12 с остатком 6, значит НОД(18, 12) = НОД(12, 6). И наконец 12 делится на 6 без остатка, значит НОД равен 6. Такой способ часто самый удобный и помогает быстро находить НОД без разложения на множители.
