НОД и НОК чисел
Рассмотрим пример решения задачи: найти НОД и НОК чисел НОД(180,200,0) = 20 НОК(180,200,0) = 1800
Укажите количество чисел:
x
x
Ответ:
НОД(180,200,0) = 20
НОК(180,200,0) = 1800
Решение:
Сначала найдем НОД - наибольший общий делитель.
Используем метод разложения на множители.
1. Представим каждое число в виде произведений простых чисел:
| Число | Множители | В эксп. форме | ||
|---|---|---|---|---|
| 180 | = | 2×2×3×3×5 | = | 22 × 32 × 51 |
| 200 | = | 2×2×2×5×5 | = | 23 × 52 |
2. Найдем общие множители. Это множители которые есть в каждом числе. И они выделены жирным
3. Найдем множители с меньшей степенью. Из каждого жирного множителя найдем один с наименьшей степенью и выделим его красным
4. Перемножение всех красных множителей определит наибольший общий делитель.
| 22 × 51 | = | 20 |
Теперь найдем НОК - наименьшее общее кратное.
Найдем НОК методом разложения на множители:
1. Представим каждое число в виде произведений простых чисел:
| Число | Множители | В эксп. форме | ||
|---|---|---|---|---|
| 180 | = | 2×2×3×3×5 | = | 22 × 32 × 51 |
| 200 | = | 2×2×2×5×5 | = | 23 × 52 |
2. Найдем все уникальные множители из всех чисел.
3. Если есть одинаковые множители выберем один из них с наибольшей степенью. Такие множители выделены зеленым
4. Перемножение уникальных множителей с наибольшей степенью определяет НОК.
| 23 × 32 × 52 | = | 1800 |
Наибольший общий делитель - это наибольшее положительное целое число, на которое делятся без остатка заданные числа.
Наименьшее общее кратное чисел - это наименьшее число которое можно разделить на все заданные числа без остатка.
Как найти НОД
- Метод перебора делителей
Этот метод может быть трудоемким для больших чисел.
Способ заключается в подборе все делителей чисел и выбора наибольшего из общих.Пример:
Найдем НОД для чисел 12 и 18.
Делители числа 12: 1, 2, 3, 4, 6, 12.
Делители числа 18: 1, 2, 3, 6, 9, 19.
Общие делители 1, 2, 3, 6.
Ответ:НОД(12,18) = 6. - Разложение на простые множители
Суть метода представить каждое число в виде умножения простых чисел.
Способ хорошо подходит для небольших чисел и может найти НОД для нескольких чисел одноврменно.
Алгоритм:
Разложите каждое из чисел на множители методом деления.
Найдите все общие множители - это такие множители которые есть в каждом из заданных чисел.
Из Них выберите множители у которых наименьшая степень.
Перемножьте их между собой и получится НОД.Пример:НОД(12,18)
Общие множители с минимальными степенями: 21 * 31 = 6Число Множители В эксп. форме 12 = 2×2×3 = 22 × 31 18 = 2×3×3 = 21 × 32 - Алоритм Евклида
Самый удобный метод. Хорошо подходит для больших чисел. Но только для двух чисел за один расчет.
Алгоритм:
Делим большее число на меньшее и находим остаток.
Делим меньшее из чисел на остаток от предыдущего деления.
Потовряем процесс до тех пор пока остаток от деления не станет равен нулю.
НОД равен последнему ненулевому остатку.
Если при первом делении остаток ноль, то НОД равен меньшему из чисел.
Пример:
НОД(12,18) = 6Деление Частное Остаток 18÷12 = 1 6 12÷6 = 2 0
Как найти НОК
- Через известный НОД
Самый простой и доступный метод. Однако для его расчета требуется знание НОД и возможен только для двух чисел.
Метод основан расчете по следующей формуле:
Пример:
где a и b - заданные числа.
Отыщем НОК для чисел 12 и 18
Сначала определим НОД(12,18) = 6
- Метод разложения на простые множители
Суть метода разложить число на несколько простых чисел - множителей.
Способ подходит для любого количества чисел.
Пример:
Найдем НОК для чисел 12 и 18
Разложим эти числа на простые множители:
Если есть повторяющиеся множители то выберем один с наибольшей степенью. Такие множители отмечены зеленым.Число Множители В эксп. форме 12 = 2×2×3 = 22 × 31 18 = 2×3×3 = 21 × 32
Перемножение всех уникальных множителей с наивысшей степенью между собой даст НОК заданных чисел.22 × 32 = 36
Напомним что число НОД - это наибольшее число, а число НОК - наоборот наименьшее.