Сравнения по модулю и целочисленные задачи
Делимость помогает исследовать целые числа без выполнения полного деления и строить точные алгоритмы.
На рисунке правило превращается в модель: отметьте известные элементы, связь между ними и только затем переходите к буквенной записи.
Главная идея
Что нужно понять
Число a делится на b, если существует целое k такое, что a = bk. НОД делит оба числа, а НОК кратно каждому из них.
Разложение на простые множители позволяет находить НОД по общим множителям, а НОК — по всем множителям с наибольшими степенями.
Модуль |x| — расстояние от x до нуля, поэтому |x| = a при a > 0 распадается на два случая: x = a или x = −a. Если a < 0, решений нет.
В более сложном уравнении сначала находят точки, где выражение под модулем меняет знак, и рассматривают промежутки отдельно.
Не заучивайте запись отдельно от смысла: проговорите, что означает каждая величина и почему выбранное правило можно применить именно здесь.
Обоснование
Почему это работает
Деление с остатком единственным образом представляет число как несколько полных групп и остаток. Алгоритм Евклида работает потому, что общие делители чисел a и b совпадают с общими делителями b и остатка a mod b.
Алгоритм: Сравнения по модулю и целочисленные задачи
Число a делится на b, если существует целое k такое, что a = bk. НОД делит оба числа, а НОК кратно каждому из них.
- 1. Разложить — числа на простые множители
- 2. Выбрать нужные — степени множителей
- 3. Проверить — делением
Опорная формула
При делении a на b число a равно b, умноженному на неполное частное q, плюс остаток r; остаток неотрицателен и меньше b.
Теорема о делении с остатком.Расшифровка
Обозначения и термины
- a = bq + r
- деление a на b с неполным частным q
- 0 ≤ r < b
- условие на остаток
- НОД(a, b)
- наибольший общий делитель
- НОК(a, b)
- наименьшее общее кратное
Алгоритм
Как решать задачи
- разложить числа на простые множители
- выбрать нужные степени множителей
- проверить делением
От простого к сложному
Подробные примеры
Найдите НОД чисел 18 и 24.
- 18 = 2 · 3², 24 = 2³ · 3.
- Берём общие множители с меньшими степенями: 2 · 3.
Ответ: 6
Найдите НОД(84, 30) алгоритмом Евклида.
- 84 = 30 · 2 + 24.
- 30 = 24 · 1 + 6.
- 24 = 6 · 4, последний ненулевой остаток равен 6.
Ответ: 6
Самопроверка
Типичные ошибки
- путать НОД и НОК
- считать единицу простым числом
- допускать остаток, не меньший делителя
Проверка пониманияОбъясните тему своими словами
Представьте, что вы объясняете тему «Сравнения по модулю и целочисленные задачи» ученику младше вас. Расскажите, что означает правило, почему оно работает и как не допустить первую типичную ошибку: путать НОД и НОК
В хорошем объяснении есть:
- Вы объяснили главную идею без дословного пересказа: Число a делится на b, если существует целое k такое, что a = bk. НОД делит оба числа, а НОК кратно каждому из них.
- Вы расшифровали математическую запись словами: При делении a на b число a равно b, умноженному на неполное частное q, плюс остаток r; остаток неотрицателен и меньше b.
- Вы придумали собственный пример, выполнили алгоритм и проверили, соответствует ли ответ условию.
Закрепление материала
Мини-тест
Выберите ответ на каждый вопрос. Объяснения откроются после проверки.
Открываем мини-тест…