Наибольший общий делитель, НОД

Найти наибольший общий делитель двух чисел

НОД (a,b) - самое большое натуральное число, на которое делится и a и b.

Пример

a = 12, b = 18.

Делители числа 12 : 1, 2, 3 , 4, 6, 12.

Делители числа 18 : 1, 2, 3, 6, 9, 18.

Общий делитель чисел 12 и 18 : 1, 2, 3, 6.

Наибольший из общих делителей - 6.

Значит, НОД (12, 18) = 6.

Пример

НОД (8, 20) = 4;

НОД (10, 50) = 10;

НОД (4, 94) = 2;

1. Разложить a и b на простые множители.

2. Подчеркнуть общие множители этих разложений.

3. Перемножить все подчеркнутые множители одного из чисел.

Пример

a = 72 = 2 • 2 • 2 • 3 • 3;

b = 96 = 2• 2• 2 • 2 • 2 • 3;

НОД (72, 96) = 2 • 2 • 2 • 3 = 24.

Пример

a = 630 = 2 • 3 • 3 • 5 • 7;

b = 3675 = 3 • 5 • 5 • 7 • 7;

НОД (630, 3675) = 3 • 5 • 7 = 105.

! Схема подходит и для нахождения НОД трех и более чисел.

Пример

220 = 2 • 2 • 5 • 11;

105 = 3 • 5 • 7;

30 = 2 • 3 • 5;

НОД (220, 105, 30) = 5.

1. Разложим 2 числа (12 и 18) на простые множители;

2. Оставляем равные множители;

3. Находим произведение множителей первой и второй группы;

Аналогичным образом можно найти наибольший общий делитель для 3, 4, 5 и более чисел.