Глава

Модульная арифметика

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

Теория

1. Остатки Когда целое число \(a\) делится на положительное целое число \(m\), его можно записать в виде \[ a=mq+r,\qquad 0\le r Число \(r\) называется остатком. Модульная арифметика позволяет работать с остатками вместо больших чисел. 2. Сравнение по модулю Запись \[ a\equiv b\pmod m \] означает, что \(a\) и \(b\) дают одинаковый остаток при делении на \(m\). Равносильно: \[ m\mid a-b. \] Например, \(17\equiv2\pmod5\), потому что \(17-2=15\) делится на \(5\). 3. Действия со сравнениями Если \[ a\equiv b\pmod m,\qquad c\equiv d\pmod m, \] то \[ a+c\equiv b+d\pmod m, \] \[ ac\equiv bd\pmod m. \] То есть остатки можно складывать, вычитать и умножать. 4. Степени и циклы Степени часто повторяются по модулю. Например, по модулю \(10\): \[ 2^1\equiv2,\quad 2^2\equiv4,\quad 2^3\equiv8,\quad 2^4\equiv6,\quad 2^5\equiv2. \] Последние цифры степеней двойки повторяются циклом длины \(4\): \(2,4,8,6\). 5. Противоречие по модулю Чтобы доказать, что уравнение не имеет целых решений, можно рассмотреть обе части по небольшому модулю. Если возможные остатки не совпадают, уравнение невозможно. Например, квадрат целого числа не может давать остаток \(2\) при делении на \(4\), потому что квадраты дают только \(0\) или \(1\pmod4\). 6. Признаки делимости как модульная арифметика Правила с цифрами объясняются через модули. Так как \[ 10\equiv1\pmod9, \] каждая степень \(10\) тоже сравнима с \(1\pmod9\). Поэтому число имеет тот же остаток по модулю \(9\), что и сумма его цифр.

Примеры

Пример 1. Остаток числа Этот пример связывает обычное деление с остатками: число нужно записать в виде \(mq+r\), где \(0\le r Задача. Найдите остаток от деления \(137\) на \(5\). Решение. Так как \(137=5\cdot27+2\), остаток равен \(2\). Пример 2. Записать сравнение Этот пример показывает, что сравнение по модулю записывает остаток после деления. Задача. Заполните пропуск: \(83\equiv \square \pmod 7\), где в пропуске одно из чисел \(0,1,2,3,4,5,6\). Решение. \(83=7\cdot11+6\), значит \(83\equiv6\pmod7\). Пример 3. Сложение остатков Этот пример учит складывать остатки, а затем упрощать результат по модулю. Задача. Если \(a\equiv4\pmod9\) и \(b\equiv7\pmod9\), найдите \(a+b\pmod9\). Решение. \(a+b\equiv4+7=11\equiv2\pmod9\). Пример 4. Последняя цифра степени Этот пример показывает, что последние цифры степеней повторяются циклами. Задача. Найдите последнюю цифру числа \(2^{25}\). Решение. Длина цикла равна \(4\). Так как \(25\equiv1\pmod4\), число \(2^{25}\) имеет ту же последнюю цифру, что и \(2^1\), то есть \(2\). Пример 5. Степень по модулю семь Этот пример учит использовать цикл степеней по модулю \(7\), чтобы не вычислять большую степень. Задача. Найдите остаток от деления \(3^{20}\) на \(7\). Решение. По модулю \(7\): \(3^1\equiv3\), \(3^2\equiv2\), \(3^3\equiv6\), \(3^4\equiv4\), \(3^5\equiv5\), \(3^6\equiv1\). Так как \(20\equiv2\pmod6\), получаем \(3^{20}\equiv3^2\equiv2\pmod7\). Пример 6. Квадраты по модулю четыре Этот пример показывает важный факт: квадрат целого числа имеет не все остатки по модулю \(4\). Задача. Докажите, что квадрат любого целого числа сравним с \(0\) или \(1\pmod4\). Решение. Если \(n=2k\), то \(n^2=4k^2\equiv0\pmod4\). Если \(n=2k+1\), то \(n^2=4k^2+4k+1\equiv1\pmod4\). Пример 7. Квадрат такого вида невозможен Этот пример учит доказывать невозможность решений через противоречие по модулю. Задача. Докажите, что уравнение \(x^2=4y+2\) не имеет целых решений. Решение. Правая часть удовлетворяет \(4y+2\equiv2\pmod4\). Но квадрат дает только \(0\) или \(1\pmod4\). Получаем противоречие. Пример 8. Всегда делится на пять Этот пример показывает, как проверка всех остатков по модулю \(5\) дает доказательство для любого целого \(n\). Задача. Докажите, что \(5\mid n^5-n\) для любого целого \(n\). Решение. Достаточно проверить \(n\equiv0,1,2,3,4\pmod5\). Получаем \(0^5-0=0\), \(1^5-1=0\), \(2^5-2=30\), \(3^5-3=240\), \(4^5-4=1020\), и все эти числа делятся на \(5\). Поэтому \(5\mid n^5-n\).

Задачи

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

Лестницы

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

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

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