НОД и НОК — это основополагающие концепции теории чисел, используемые при упрощении дробей, решении уравнений и задачах планирования. Здесь каждый метод объяснен ясно.
Определения
НОД (наибольший общий делитель) — также называемый НКО (наибольший общий делитель) или НКО (наивысший общий делитель) — это наибольшее положительное целое число, которое делит оба числа без остатка.
LCM (наименьшее общее кратное) — это наименьшее положительное целое число, которое делится на оба числа.
GCD(a, b) × LCM(a, b) = a × b
Это соотношение означает, что, найдя одно, вы можете вычислить другое:
LCM(a, b) = (a × b) ÷ GCD(a, b)
Метод 1: факторизация простых чисел
Подходит для: понимания, небольших чисел, нескольких чисел одновременно.
Шаги для НОД:
- Разложите на множители каждое число.
- Найдите общие простые множители
- Умножьте наименьшие степени общих множителей.
Шаги для LCM:
- Разложите на множители каждое число.
- Умножьте высшие степени всех простых множителей.
Пример: НОД и НОК чисел 36 и 48.
Премьер-факторизация:
- 36 = 2² × 3²
- 48 = 2⁴ × 3
НОД: Общие множители – 2 и 3. Возьмем наименьшую степень:
- НОД = 2² × 3¹ = 4 × 3 = 12
LCM: Все факторы. Возьмите высшие силы:
- LCM = 2⁴ × 3² = 16 × 9 = 144
Проверьте: 36 × 48 = 1728 = 12 × 144 ✓
Способ 2: алгоритм Евклида (НОД)
Наилучший вариант: Большие числа — гораздо быстрее, чем факторизация.
Ключевая идея: НОД(a, b) = НОД(b, a mod b), повторяя до тех пор, пока остаток не станет равен 0.
GCD(a, b):
while b ≠ 0:
r = a mod b
a = b
b = r
return a
Пример: НОД(252, 105)
| Шаг | а | б | г = мод b |
|---|---|---|---|
| 1 | 252 | 105 | 42 |
| 2 | 105 | 42 | 21 |
| 3 | 42 | 21 | 0 |
НОД = 21 (последний ненулевой остаток)
Пример: НОД(1071, 462)
| Шаг | а | б | р |
|---|---|---|---|
| 1 | 1071 | 462 | 147 |
| 2 | 462 | 147 | 21 |
| 3 | 147 | 21 | 0 |
НОД = 21
Метод 3: метод деления/лестницы
Наилучший вариант для: Визуальных учащихся, которые одновременно находят и НОД, и НОК.
Разделите оба числа на их наименьший общий простой делитель несколько раз:
Пример: НОД и НОК чисел 12 и 18.
2 | 12 18
3 | 6 9
| 2 3
НОД = произведение использованных делителей = 2 × 3 = 6 LCM = произведение делителей × оставшиеся числа = 2 × 3 × 2 × 3 = 36
LCM для более чем двух номеров
Пример: НОК(4, 6, 10)
Премьер-факторизация:
- 4 = 2²
- 6 = 2 × 3
- 10 = 2 × 5
Возьмите наибольшую степень каждого простого числа: 2² × 3 × 5 = 60.
Проверьте: 60 ÷ 4 = 15 ✓, 60 ÷ 6 = 10 ✓, 60 ÷ 10 = 6 ✓
Реальные приложения
Упрощение дробей. Разделите числитель и знаменатель на их НОД.
- 24/36: НОД(24,36) = 12 → 24/36 = 2/3
Сложение дробей с разными знаменателями: Найдите НОК знаменателей.
- 1/4 + 1/6: НОК(4,6) = 12 → 3/12 + 2/12 = 5/12
Проблемы с расписанием: «Одновременно отправляются два автобуса. Один ходит каждые 12 минут, другой — каждые 18 минут. Когда они снова отправятся вместе?»
- LCM(12, 18) = 36 → каждые 36 минут
Материалы для резки: «Одна доска — 36 см, другая — 48 см. Какой самый длинный кусок одинаковой длины можно вырезать из обеих досок без отходов?»
- НОД(36, 48) = 12 см
Быстрые психологические проверки
НОД всегда ≤ меньшее число LCM всегда ≥ большего числа Если НОД(a,b) = 1, числа взаимно простые — НОК(a,b) = a × b
Пример: НОД(7, 13) = 1 (оба простые, нет общих делителей) → НОК = 7 × 13 = 91