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

Наибольший общий делитель чисел a и b — наибольшее натуральное число, на которое делятся и a, и b. Обозначение — НОД(a, b). Например, НОД(24, 36) = 12: делители 24 — 1, 2, 3, 4, 6, 8, 12, 24, делители 36 — 1, 2, 3, 4, 6, 9, 12, 18, 36, наибольший общий — 12.

Алгоритм Евклида

Большее число делят на меньшее с остатком, затем делитель — на остаток, и так до нулевого остатка. Последний ненулевой остаток — НОД.

Пример: 36 = 24 · 1 + 12; 24 = 12 · 2 + 0. НОД(24, 36) = 12.

Алгоритм работает быстро даже для больших чисел: не нужно раскладывать их на множители.

НОД через разложение на простые множители

1. Разложите числа на простые множители.
2. Возьмите множители, которые есть во всех разложениях, в наименьшей степени.
3. Перемножьте их.

Пример: 24 = 2³ · 3, 36 = 2² · 3². НОД = 2² · 3 = 12.

НОД нескольких чисел

НОД находят по очереди: НОД(a, b, c) = НОД(НОД(a, b), c). Для 60, 90 и 150: НОД(60, 90) = 30, НОД(30, 150) = 30.

Вопросы и ответы

Зачем нужен НОД?

Чтобы сокращать дроби: числитель и знаменатель делят на их НОД. 24/36 = (24 : 12) / (36 : 12) = 2/3 — дробь несократимая.

Что такое взаимно простые числа?

Числа, у которых НОД равен 1: например, 17 и 13 или 8 и 9. Дробь из взаимно простых чисел несократимая.

Как связаны НОД и НОК?

Для двух чисел НОД(a, b) · НОК(a, b) = a · b. Для 24 и 36: 12 · 72 = 864 = 24 · 36. НОК можно найти калькулятором НОК.

Чему равен НОД числа и его делителя?

Самому делителю: если 12 делится на 4, то НОД(12, 4) = 4.