НОД, НОК и деление с остатком · 6 класс

Главная идея

Что нужно понять

Число a делится на b, если существует целое k такое, что a = bk. НОД делит оба числа, а НОК кратно каждому из них.

Разложение на простые множители позволяет находить НОД по общим множителям, а НОК — по всем множителям с наибольшими степенями.

Алгоритм Евклида заменяет пару чисел делителем и остатком, сохраняя их общие делители. Последний ненулевой остаток и есть НОД исходных чисел.

Связь НОД(a, b) · НОК(a, b) = a · b для положительных чисел даёт дополнительную проверку. В делении с остатком остаток всегда неотрицателен и строго меньше делителя.

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

Обоснование

Почему это работает

Деление с остатком единственным образом представляет число как несколько полных групп и остаток. Алгоритм Евклида работает потому, что общие делители чисел a и b совпадают с общими делителями b и остатка a mod b.

Опорная формула

a=bq+r,\qquad 0\le r<b

Формула словами

При делении a на b число a равно b, умноженному на неполное частное q, плюс остаток r; остаток неотрицателен и меньше b.

Теорема о делении с остатком.

Расшифровка

Обозначения и термины

a = bq + r: деление a на b с неполным частным q
0 ≤ r < b: условие на остаток
НОД(a, b): наибольший общий делитель
НОК(a, b): наименьшее общее кратное

Алгоритм

Как решать задачи

разложить числа на простые множители
выбрать нужные степени множителей
проверить делением

От простого к сложному

Подробные примеры

Пример 1

Найдите НОД чисел 18 и 24.

18 = 2 · 3², 24 = 2³ · 3.
Берём общие множители с меньшими степенями: 2 · 3.

Ответ: 6

Пример 2

Найдите НОД(84, 30) алгоритмом Евклида.

84 = 30 · 2 + 24.
30 = 24 · 1 + 6.
24 = 6 · 4, последний ненулевой остаток равен 6.

Ответ: 6

Самопроверка

Типичные ошибки

путать НОД и НОК
считать единицу простым числом
допускать остаток, не меньший делителя