Сравнения по модулю и целочисленные задачи

Главная идея

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

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

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

Модуль |x| — расстояние от x до нуля, поэтому |x| = a при a > 0 распадается на два случая: x = a или x = −a. Если a < 0, решений нет.

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

Обоснование

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

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

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

a = bq + r

деление a на b с неполным частным q

0 ≤ r < b

условие на остаток

НОД(a, b)

наибольший общий делитель

НОК(a, b)

наименьшее общее кратное

Алгоритм

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

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

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

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

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