Глава

Сравнения и остатки

Классы остатков, линейные сравнения, совместимые остатки и олимпиадные рассуждения по модулю.

Теория

1. Классы остатков По модулю \(m\) каждое целое число попадает ровно в один из классов \[ 0,1,2,\ldots,m-1. \] Например, по модулю \(5\) число \(23\) находится в классе \(3\), потому что \[ 23\equiv3\pmod5. \] 2. Сравнение как инструмент Запись \[ a\equiv b\pmod m \] означает, что \(a-b\) делится на \(m\). Это превращает задачи с большими числами в задачи о маленьких остатках. 3. Решение линейных сравнений Сравнение вида \[ ax\equiv b\pmod m \] называется линейным сравнением. Если \(\gcd(a,m)=1\), то у \(a\) есть обратный элемент по модулю \(m\), и сравнение имеет ровно одно решение по модулю \(m\). Пример: \[ 3x\equiv5\pmod7. \] Так как \(3\cdot5\equiv1\pmod7\), умножаем обе части на \(5\): \[ x\equiv25\equiv4\pmod7. \] 4. Почему делить опасно В обычных уравнениях мы часто делим обе части. В сравнениях деление разрешено только тогда, когда делитель обратим по модулю. Например, \[ 2x\equiv2\pmod6 \] нельзя просто разделить на \(2\) и получить только \(x\equiv1\pmod6\). На самом деле решения: \[ x\equiv1,4\pmod6. \] 5. Совместимые остатки Иногда число должно удовлетворять нескольким условиям: \[ n\equiv a\pmod m,\qquad n\equiv b\pmod k. \] Когда модули маленькие, можно выписать один класс остатков и проверить второе условие. Это подготовка к китайской теореме об остатках. 6. Остатки в олимпиадных задачах Остатки помогают доказывать невозможность, находить вид числа или сокращать много случаев до нескольких. Полезные вопросы: Какой модуль делает выражение проще? Какие остатки возможны? Может ли общий делитель, квадрат или степень дать противоречие?

Примеры

Пример 1. Класс остатка Этот пример показывает, как стандартный остаток задаёт класс остатка числа по выбранному модулю. Задача. Найдите класс остатка числа \(94\) по модулю \(9\). Решение. Так как \(94=9\cdot10+4\), получаем \(94\equiv4\pmod9\). Пример 2. Отрицательный остаток Этот пример напоминает, что отрицательные числа тоже нужно приводить к стандартным остаткам от 0 до m-1. Задача. Запишите \(-17\) как стандартный остаток по модулю \(6\). Решение. \(-17+18=1\), значит \(-17\equiv1\pmod6\). Пример 3. Равносильные сравнения Этот пример связывает запись сравнения с условием делимости, которое стоит за этой записью. Задача. Объясните, почему \(a\equiv b\pmod m\) равносильно \(m\mid a-b\). Решение. Если \(a=mq+r\) и \(b=mk+r\), то \(a-b=m(q-k)\), значит \(m\mid a-b\). Обратно, если \(m\mid a-b\), то числа отличаются на кратное \(m\), поэтому имеют одинаковый остаток по модулю \(m\). Пример 4. Решить простое сравнение Этот пример показывает, как решить линейное сравнение с помощью обратного элемента по модулю. Задача. Решите \(4x\equiv3\pmod7\). Решение. Так как \(4\cdot2=8\equiv1\pmod7\), умножаем обе части на \(2\). Получаем \(x\equiv6\pmod7\). Пример 5. Два решения Этот пример показывает, как решить линейное сравнение с помощью обратного элемента по модулю. Задача. Решите \(2x\equiv4\pmod6\). Решение. Проверяя остатки по модулю \(6\), видим, что подходят \(x=2\) и \(x=5\). Значит, \(x\equiv2,5\pmod6\). Иначе: после деления на \(2\) получаем \(x\equiv2\pmod3\), что дает остатки \(2\) и \(5\) по модулю \(6\). Пример 6. Совместимые остатки I Этот пример учит выписывать один класс остатков и проверять второе условие. Задача. Найдите наименьшее положительное целое \(n\), такое что \(n\equiv2\pmod3\) и \(n\equiv1\pmod5\). Решение. Числа \(1\pmod5\): \(1,6,11,16,\ldots\). Проверяя по модулю \(3\), получаем \(1,0,2,1,\ldots\). Первое подходящее число - \(11\). Пример 7. Остаток многочлена Этот пример показывает, что выражение по модулю удобно считать после приведения переменной к остатку. Задача. Если \(n\equiv5\pmod8\), найдите \(n^2+3n+1\pmod8\). Решение. \(n^2+3n+1\equiv5^2+3\cdot5+1=25+15+1=41\equiv1\pmod8\). Пример 8. Сравнимые квадраты Этот пример показывает, как доказывать свойство сравнений умножением сравнимых величин. Задача. Докажите: если \(a\equiv b\pmod m\), то \(a^2\equiv b^2\pmod m\). Решение. Так как \(a\equiv b\pmod m\), можно перемножить сравнения: \(a\cdot a\equiv b\cdot b\pmod m\). Значит, \(a^2\equiv b^2\pmod m\).

Задачи

Пока нет опубликованных задач.

Лестницы

Опубликованных лестниц пока нет.

Предыдущая глава

Следующая глава