НОД, НОК и алгоритм Евклида

  • 5 мин чтения
  • Послушать — 2 мин
  • 10 карточек

Алгебра, 7 класс · С. М. Никольский, М. К. Потапов, Н. Н. Решетников, А. В. Шевкин

По разложению. НОД — произведение общих простых множителей, каждый в наименьшей степени; НОК — произведение всех простых множителей, каждый в наибольшей степени: 120 = 2³ · 3 · 5, 126 = 2 · 3² · 7, НОД = 2 · 3 = 6, НОК = 2³ · 3² · 5 · 7 = 2520. Всегда НОК(a, b) · НОД(a, b) = a · b.

Алгоритм Евклида не требует разложения: делим большее число на меньшее с остатком, затем меньшее — на остаток, и так далее; последний ненулевой остаток — НОД.

203 = 91 · 2 + 21, 91 = 21 · 4 + 7, 21 = 7 · 3 — НОД(203, 91) = 7.

Если НОД равен 1, числа взаимно простые.

Квадраты из прямоугольника. От прямоугольника a × b (a > b) отрезают квадраты со стороной b, сколько поместится, — это неполное частное a : b; из остатка b × r — квадраты со стороной r, и т. д. Всего квадратов — сумма неполных частных алгоритма Евклида, а сторона самого маленького — НОД(a, b).

Правило

1 / 10

НОД по разложению

Чтобы найти наибольший общий делитель, разложим числа на простые множители и вычислим произведение всех их общих простых множителей, взяв каждый в наименьшей степени.

90 = 2 · 3² · 5, 84 = 2² · 3 · 7

НОД(90, 84) = 2 · 3 = 6

Правило

2 / 10

НОК по разложению

Чтобы найти наименьшее общее кратное, вычислим произведение всех простых множителей, взяв каждый в наибольшей степени, встречающейся в разложениях.

90 = 2 · 3² · 5, 84 = 2² · 3 · 7

НОК(90, 84) = 2² · 3² · 5 · 7 = 1260

Разбор

3 / 10

НОК через НОД

НОК(a, b) · НОД(a, b) = a · b

  1. Обозначим

    Пусть НОД(a, b) = d. Тогда a = m · d, b = n · d, где m и n не имеют общих простых делителей.

  2. Кратное

    Тогда НОК(a, b) = m · n · d.

  3. Произведение

    (m · n · d) · d = (m · d) · (n · d) = a · b

  4. Ответ

    Например, НОК(90, 84) = 90 · 84 : 6 = 1260.

Проверь себя

4 / 10

Найди НОК

НОД(12, 18) = 6

Чему равно НОК(12, 18)?

216366
Ответ и объяснение

12 · 18 : 6 = 36.

Разбор

5 / 10

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

Делим большее число на меньшее с остатком, затем меньшее на остаток и так далее. НОД равен последнему отличному от нуля остатку.

Вычислим НОД(133, 56).

  1. Шаг 1

    133 = 56 · 2 + 21

  2. Шаг 2

    56 = 21 · 2 + 14

  3. Шаг 3

    21 = 14 · 1 + 7

  4. Шаг 4

    14 = 7 · 2

  5. Ответ

    НОД(133, 56) = 7

Правило

6 / 10

Почему это верно

Просматривая цепочку равенств снизу вверх, находим, что последний ненулевой остаток — общий делитель чисел a и b.

Просматривая её сверху вниз, находим, что любой общий делитель a и b является делителем этого остатка.

Значит, этот остаток и есть наибольший общий делитель.

Пример

7 / 10

Взаимно простые

90 = 83 · 1 + 7, 83 = 7 · 11 + 6

7 = 6 · 1 + 1, 6 = 1 · 6

НОД(83, 90) = 1: числа 83 и 90 взаимно простые.

Поэтому НОК(83, 90) = 83 · 90 : 1 = 7470.

Разбор

8 / 10

Квадраты из прямоугольника

Прямоугольник 17 на 5 на клетках разрезан на 3 квадрата со стороной 5, 2 квадрата со стороной 2 и 2 квадрата со стороной 1
Прямоугольник 17 на 5 на клетках разрезан на 3 квадрата со стороной 5, 2 квадрата со стороной 2 и 2 квадрата со стороной 1

На сколько квадратов можно разрезать прямоугольник 17 × 5, если каждый раз отрезать наибольший квадрат?

  1. Шаг 1

    17 = 5 · 3 + 2: три квадрата со стороной 5.

  2. Шаг 2

    5 = 2 · 2 + 1: два квадрата со стороной 2.

  3. Шаг 3

    2 = 1 · 2: два квадрата со стороной 1.

  4. Ответ

    3 + 2 + 2 = 7 квадратов.

Проверь себя

9 / 10

Сколько квадратов

Прямоугольник 13 × 5 разрезают, каждый раз отрезая наибольший квадрат.

Сколько получится квадратов?

456
Ответ и объяснение

13 = 5 · 2 + 3, 5 = 3 · 1 + 2, 3 = 2 · 1 + 1, 2 = 1 · 2: 2 + 1 + 1 + 2 = 6.

Главное

10 / 10

Главное

  • НОД: общие множители в наименьшей степени.
  • НОК: все множители в наибольшей степени.
  • НОК(a, b) · НОД(a, b) = a · b
  • Алгоритм Евклида: НОД — последний ненулевой остаток.
  • НОД равен 1: числа взаимно простые.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест