Перейти к содержимому
Topos Uranos
Русский

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

Краткое содержание

Этот урок превращает классификацию целых чисел по остаткам в исчисление. Он определяет сравнение по модулю nn, доказывает, что сравнимость равносильна равенству остатков, что сравнение является отношением эквивалентности и что оно согласовано со сложением, умножением и возведением в степень, и строит из его классов множество Zn\mathbb{Z}_n остатков с таблицами сложения и умножения. С помощью соотношения Безу он выясняет, какие остатки имеют обратный, и полностью решает линейные сравнения; доказывает китайскую теорему об остатках и малую теорему Ферма, заново прочитывает признаки делимости как сравнения и применяет всё это к контрольным цифрам, к календарю и к криптосистеме RSA, корректность которой доказывается.

Цели обучения

  1. Доказывать, что сравнение по модулю nn является отношением эквивалентности, согласованным со сложением, умножением и возведением в степень, и использовать его для вычисления остатков больших чисел.
  2. Строить таблицы сложения и умножения в Zn\mathbb{Z}_n и выяснять с помощью наибольшего общего делителя, какие остатки имеют обратный.
  3. Выяснять, имеет ли линейное сравнение решение, вычислять, сколько решений оно имеет по модулю nn, и находить их все.
  4. Решать системы сравнений с взаимно простыми модулями с помощью китайской теоремы об остатках, строя решение и доказывая его единственность.
  5. Доказывать малую теорему Ферма и применять её к остаткам степеней, к свойствам делимости, верным для всех целых чисел, и к корректности системы RSA.
  6. Анализировать, какие ошибки обнаруживает контрольная цифра, и вычислять дни недели с помощью сравнений.

Отношение сравнения

Если сегодня понедельник, то через 1515 дней будет вторник, а через 10001000 дней будет воскресенье: чтобы это узнать, не нужно отсчитывать дни один за другим, достаточно остатка от деления числа дней на 77. Точно так же через 55 часов после 99 часов будет 22 часа на циферблате с 1212 делениями, а последняя цифра произведения зависит только от последних цифр множителей. Во всех трёх случаях вычисляют с остатками и забывают о частном. Урок о делимости и делении с остатком распределил целые числа по классам в зависимости от остатка при делении на натуральное число и доказал, что остаток суммы, произведения и степени зависит только от остатков данных чисел. Этот урок даёт этим наблюдениям собственный язык, язык сравнений, который Гаусс ввёл в 1801 году в своих Disquisitiones Arithmeticae, и превращает его в инструмент вычислений. Как и в том уроке, целые числа используются заранее, вместе с правилами их арифметики и порядка, обоснованными в уроке о целых числах.

Определение (сравнение). Пусть nn есть натуральное число. Два целых числа aa и bb сравнимы по модулю nn, если nn делит их разность a−ba - b. Пишут a≡b(modn)a \equiv b \pmod{n} и читают «aa сравнимо с bb по модулю nn»; натуральное число nn называется модулем сравнения.
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

Так, 17≡2(mod5)17 \equiv 2 \pmod{5}, поскольку 17−2=1517 - 2 = 15; −3≡9(mod4)-3 \equiv 9 \pmod{4}, поскольку −3−9=−12-3 - 9 = -12; а целое число чётно в точности тогда, когда оно сравнимо с 00 по модулю 22. То, что aa кратно nn, записывается теперь как a≡0(modn)a \equiv 0 \pmod{n}. По модулю 11 все целые числа сравнимы между собой, поскольку 11 делит любое целое число; этот случай не представляет интереса, и в примерах модуль будет не меньше 22. Знак ≡\equiv из трёх черт напоминает знак равенства, поскольку, как будет видно, сравнение почти во всём ведёт себя как равенство; исключением, делением, займётся параграф об обратных.

Определение через разность удобнее всего для доказательств, но интуиция начальных примеров связана с остатком. Следующее утверждение гарантирует, что оба описания говорят одно и то же; его содержание уже отмечалось, в другой форме, в уроке о делимости при обосновании признаков делимости, а здесь оно доказывается со всеми шагами.

УтверждениеСравнение и остаток

Два целых числа сравнимы по модулю nn тогда и только тогда, когда они дают одинаковый остаток при делении на nn. Пусть a=nq+ra = nq + r и b=ns+tb = ns + t суть деления с остатком чисел aa и bb на nn, где 0≤r<n0 \leq r < n и 0≤t<n0 \leq t < n. Рисунок располагает целые числа от −10-10 до 2424 рядами по 55, так что каждый столбец собирает числа с одинаковым остатком.

Доказательство

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    Если остатки совпадают, r=tr = t, то при вычитании двух делений остаток сокращается, и разность кратна nn.

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    Обратно, предположим, что nn делит a−ba - b, то есть что a=b+nka = b + nk для некоторого целого kk. Подставим деление числа bb.

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    Поскольку 0≤t<n0 \leq t < n, это равенство есть деление aa на nn с остатком tt. В силу единственности неполного частного и остатка tt является остатком числа aa, то есть t=rt = r.

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    На рисунке −7-7, −2-2, 33, 88, 1313, 1818 и 2323 стоят в одном столбце: все они дают остаток 33, а их разности кратны 55.

В частности, всякое целое число сравнимо по модулю nn со своим остатком, который является одним из nn целых чисел 0,1,…,n−10, 1, \ldots, n - 1, и только с одним из них, поскольку два таких числа сами являются своими остатками и, если они различны, дают различные остатки. Вычислять по модулю nn значит заменять каждое число удобным представителем его столбца: остатком или иногда небольшим отрицательным числом, например −1-1 вместо n−1n - 1.