Наибольший общий делитель
В математике есть понятие «делимость». Оно означает, что одно число можно разделить на другое без остатка. Например, 12 делится на 3 без остатка:
12 : 3 = 4.
Если число делится само на себя и на единицу, то оно называется простым числом. Если же число имеет другие делители, кроме 1 и самого числа, то это составное число.
У каждого числа есть общие делители с другими числами. Но среди них есть наибольший общий делитель (НОД). Это наибольшее число, на которое оба числа делятся без остатка.
Чтобы найти НОД двух чисел, нужно выполнить следующие шаги:
Рассмотрим пример нахождения НОД чисел 24 и 36.
Разложим эти числа на простые множители:
24 = 2 2 2 3;36 = 2 2 3 3.
Общие простые множители этих чисел — 2 и 3. Их произведение равно 4. Значит, НОД (24; 36) = 4.
Также для нахождения наибольшего общего делителя можно использовать другой способ — алгоритм Евклида. Он заключается в последовательном делении большего числа на меньшее с остатком. Затем меньшее число заменяют на остаток от деления. Этот процесс повторяют до тех пор, пока не получится ноль. Последний ненулевой остаток и будет НОД данных чисел.
Например, найдём НОД чисел 84 и 21.
84 / 21 = 4 (остаток 0).
Теперь заменим 21 на остаток 0.
84 / 0 = (невозможно).
Значит, НОД (84; 21) = 21.
Вопросы:
Примеры:
Найдите НОД следующих чисел:
а) 18 и 24; б) 72 и 96; в) 56 и 70.
Решение:
а) Разложим числа 18 и 24 на простые множители:
18 = 2 3 3,24 = 2 2 2 * 3.
Общими простыми множителями являются 2 и 3. Перемножим их: 2 * 3 = 6. Значит, НОД (18; 24) = 6.
б) Разложим числа 72 и 96 на простые множители:
72 = 2 2 2 3 3,96 = 2 2 2 2 2 * 3.
Общим простым множителем является 2 2 2 3. Его произведение равно 4 3 = 12. Значит, НОД (72; 96) = 12.
в) Разложим числа 56 и 70 на простые множители:
56 = 2 2 2 7,70 = 2 5 * 7.
Общий простой множитель — 7. Значит, НОД (56; 70) = 7.