MindCube Академия - Наибольший общий делитель

Число $45$ имеет следующие делители: $1,\ 3,\ 5,\ 9,\ 15,\ 45$ .

Число $60$ имеет следующие делители: $1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 10,\ 12,\ 15,\ 20,\ 30,\ 60$ .

Для чисел $45$ и $60$ общими делителями являются: $1,\ 3,\ 5,\ 15$ , из которых наибольший — это $15$ .

Определение

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

Наибольший общий делитель чисел $a$ и $b$ обозначают как $НОД (a;\ b)$ .

$НОД(36;\ 64) = 4$ .

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

$\blacktriangleright$ Пример. Найдем $НОД (231;\ 546)$ .

$231=3\cdot 7\cdot 11$ ,

$546=2\cdot 3\cdot 7\cdot 13$ .

Общими простыми делителями для данных чисел являются числа $3$ и $7$ .

Наибольшее число, на которое нацело делятся и $231$ , и $546$ , равно $3\cdot 7$ , то есть $НОД (231;\ 546) = 3\cdot 7 = 21$ .

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

	Шаги алгоритма	Например, найдём $НОД (360; 660)$
1	Разложить данные числа на простые множители.	$360=2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5$ , $660=2\cdot 2\cdot 3\cdot 5\cdot 11$ . Запишем разложение данных чисел на простые множители в виде произведения степеней: $360=2^3\cdot 3^2\cdot 5^1$ , $660=2^2\cdot 3^1\cdot 5^1\cdot 11^1$ .
2	Взять степени, основания которых являются общими простыми множителями.	В данном примере это основания $2, 3$ и $5$ .
3	Из каждой пары степеней с одинаковым основанием выбрать степень с меньшим показателем.	В данном примере это $2^2, 3^1$ и $5^1$ .
4	Перемножить выбранные степени; полученное произведение будет являться наибольшим общим делителем данной пары чисел.	$НОД (360; 660) = 2^2\cdot 3^1\cdot 5^1 = 60$ .

$\blacktriangleright$ Пример. Найдём $НОД (364;\ 825)$ .

$364=2^2\cdot 7\cdot 13$ ,

$825=3\cdot 5^2\cdot 11$ .

Числа $364$ и $825$ не имеют общих простых делителей. $НОД (364;\ 825)=1$ .

Числа $364$ и $825$ — взаимно простые.

Отметим, что любые два простых числа являются взаимно простыми.

$\blacktriangleright$ Пример. Найдём $НОД (550;\ 2200)$ .

Нет необходимости раскладывать данные числа на простые множители. Число $550$ — делитель числа $2200$ . Поэтому $НОД (550;\ 2200)=550$ .

Если число $a$ — делитель числа $b$ , то $НОД(a;\ b)=a.$

Можно находить наибольший общий делитель любого количества натуральных чисел.

$\blacktriangleright$ Пример. Найдём $НОД(48;\ 72;\ 120)$ .

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

$48 = 2^4 \cdot 3$ ,

$72 = 2^3 \cdot 3^2$ ,

$120 = 2^3 \cdot 3 \cdot 5$ .

$НОД(48;\ 72;\ 120) = 2^3 \cdot 3 = 24$ .