В лекции гарвардского формата, опубликованной на платформе MIT OpenCourseWare, преподаватель Бринмор Чепмен знакомит слушателей с основами модульной арифметики, широко известной как «арифметика часов». Опираясь на базовые понятия теории чисел, такие как делимость и расширенный алгоритм Евклида, лектор подробно разбирает правила сравнения чисел по модулю, особенности выполнения арифметических операций и фундаментальную Малую теорему Ферма. Этот детальный разбор демонстрирует, как инструменты абстрактной алгебры позволяют эффективно упрощать вычисления с гигантскими числами, наводя порядок в бесконечном множестве целых значений.
🧩 Повторение пройденного: от делимости к тождеству Безу 0:14
Лектор Бринмор Чепмен начинает занятие с краткого напоминания материала предыдущей недели, посвященного теории чисел и делимости. В прошлый раз студенты увидели практическое применение этих принципов для «спасения Нью-Йорка», а сегодня их ждет еще более увлекательная тема — модульная арифметика.
Преподаватель просит аудиторию твердо зафиксировать в памяти два ключевых факта из прошлых занятий, которые послужат фундаментом для текущей темы:
- Тождество Безу: для всех целых чисел $a$ и $b$ существуют такие целые коэффициенты $s$ и $t$, при которых выполняется равенство $\gcd(a, b) = as + bt$. Эти коэффициенты можно эффективно вычислить с помощью алгоритма, который лектор иронично называет «пульверизатором» (расширенным алгоритмом Евклида).
- Любое целое число может быть представлено в виде целочисленной линейной комбинации (ILC) чисел $a$ и $b$ тогда и только тогда, когда оно нацело делится на их наибольший общий делитель ($\gcd$).
⏰ «Арифметика часов»: интуиция из повседневной жизни 2:33
Модульная арифметика в той или иной форме знакома каждому человеку еще со школьной скамьи. Чтобы активизировать интуицию студентов, Чепмен предлагает аудитории решить несколько простых бытовых задач. На вопрос о том, чему равна сумма четного и нечетного чисел, студенты уверенно отвечают, что результат всегда будет нечетным.
Затем лектор задает вопрос посложнее: какая последняя цифра получится при перемножении чисел $357$ и $994$? Как оказывается, для ответа совершенно необязательно перемножать эти трехзначные числа целиком — достаточно изолировать и перемножить их последние цифры. Произведение $7 \times 4 = 28$ заканчивается на 8, следовательно, и результат огромного исходного выражения гарантированно будет оканчиваться на восьмерку.
Аналогичная логика работает и при обращении со временем. Если на часах сейчас 2:39 дня, то через 49 часов циферблат покажет 3:39. Секрет быстрого подсчета прост: 49 часов — это на один час больше, чем двое полных суток. Двое суток (48 часов) можно просто отбросить, сфокусировавшись на остатке в один час. Тот же принцип применим к дням недели: если нужно узнать, какой день наступит через 100 дней, достаточно вспомнить, что 100 дней — это ровно 14 недель и 2 дня. Отбросив полные недели, мы просто прибавляем два дня к текущему моменту и получаем четверг.
Главный методологический вывод, который формулирует Чепмен: при работе по модулю $n$ исследователь сознательно игнорирует все целые кратные числа $n$, фокусируя внимание исключительно на остатках от деления.
- При анализе четности и нечетности базовый модуль равен 2.
- При расчете дней недели модуль равен 7.
- При поиске последней цифры числа вычисления ведутся по модулю 10.
- При расчете времени модуль составляет 12 или 24.
Именно из-за цикличности временных промежутков модульную арифметику в академической среде часто называют «арифметикой часов».
📐 Математическая строгость: сравнения и классы вычетов 5:29
Переходя к строгим математическим формулировкам, преподаватель вводит базовое определение модульного сравнения. Число $a$ называется сравнимым с числом $b$ по модулю $n$, если и только если разность этих чисел $(a - b)$ нацело делится на $n$. В литературе это записывается как $a \equiv b \pmod n$.
Чепмен обращает внимание на существование альтернативной записи вида $a \equiv b \bmod n$, однако настоятельно призывает студентов избегать правого варианта написания на начальных этапах обучения. По его опыту, использование слова «mod» без скобок часто порождает путаницу между бинарным отношением эквивалентности и изолированной функцией взятия остатка, применяемой в программировании.
Если модуль $n$ делит разность чисел, их можно условно считать «равными» в рамках выбранной модульной системы. Например, если зафиксировать модуль 5, то все бесконечное множество целых чисел распадается ровно на пять уникальных, не пересекающихся между собой групп — классов вычетов:
- Класс нуля $[0]_5$, объединяющий числа $0, \pm 5, \pm 10, \pm 15$ и так далее.
- Класс единицы $[1]_5$, куда входят $1, 6, 11, -4, -9$ и другие аналогичные числа.
- Классы $[2]_5, [3]_5, [4]_5$, сформированные по абсолютно такой же аналогии.
Любое произвольное целое число $k$ гарантированно принадлежит к одному из этих пяти классов. Чтобы определить его групповую принадлежность, достаточно разделить $k$ на модуль 5 и узнать остаток. Опираясь на формулу $k = 5q + r$, где остаток $r$ строго ограничен рамками от 0 до 5, мы однозначно соотносим число с его классом вычетов.
🏛️ Теорема о делении и равенство остатков 9:31
Для подведения строгого базиса под интуитивные выводы Чепмен заставляет аудиторию вспомнить классическую теорему о делении с остатком. Согласно ей, для любой пары целых чисел $n$ и $d$ (при условии $d > 0$) существует единственная пара целых чисел $q$ (частное) и $r$ (остаток), такая что выполняется равенство $n = qd + r$ при строгом ограничении $0 \le r < d$. Частное в рамках лекции обозначается функцией $\text{div}(n, d)$, а остаток — функцией $\text{rem}(n, d)$. Преподаватель отдельно подчеркивает, что восклицательный знак после знака существования ($\exists!$) в записи теоремы указывает на абсолютную уникальность найденных $q$ и $r$ — двух разных остатков у одного деления быть не может.
При работе по модулю $n$ любое число всегда эквивалентно своему остатку от деления на этот модуль, который также называют «вычетом», а сами вычеты от $0$ до $n-1$ формируют идеальное математическое разбиение множества целых чисел.
Из этого вытекает важнейшая теорема: числа $a$ и $b$ сравнимы по модулю $n$ тогда и только тогда, когда их остатки от деления на $n$ абсолютно равны. По правилам математического анализа, доказательство этого утверждения «если и только если» требует проведения двух раздельных доказательств в противоположных направлениях:
- Доказательство в прямом направлении: мы предполагаем, что остатки чисел равны ($\text{rem}(a, n) = \text{rem}(b, n) = r$). Записав числа через теорему о делении, получаем $a = qn + r$ и $b = q'n + r$. При вычитании одного уравнения из другого остатки взаимоуничтожаются: $a - b = n(q - q')$. Разность оказалась кратна $n$, что полностью соответствует дефиниции модульной сравнимости. В качестве иллюстрации лектор приводит числа 17 и 12 по модулю 5: их разность равна 5, что кратно 5. Число 17 также будет сравнимо с 32, но оно не сравнимо с 33, поскольку разность $17 - 33 = -16$ не делится на 5 без остатка.
- Доказательство в обратном направлении: теперь мы изначально предполагаем, что $a \equiv b \pmod n$. По определению это значит, что $a = b + kn$ для некоторого целого числа $k$. Расписав число $b$ через теорему о делении как $q'n + r$, подставим его в уравнение: $a = (q'n + r) + kn = (q' + k)n + r$. В силу ранее доказанной уникальности остатков в теореме о делении, коэффициент $r$ обязан быть одинаковым для обоих чисел, что и требовалось доказать.
⚠️ Ловушки нотации и специфика языков программирования 21:13
Чепмен делает серьезное отступление, посвященное терминологическим ловушкам. В рамках текущего академического курса принята строгая конвенция: остаток $\text{rem}(a, n)$ всегда обязан быть неотрицательным числом, находящимся в диапазоне между $0$ и $n$, даже если делимое или сам модуль являются отрицательными числами.
Однако за пределами математических кафедр, особенно в сфере компьютерных наук и практического программирования, дела обстоят иначе. Операторы взятия остатка (будь то знак процента %, ключевые слова rem или mod) ведут себя в разных языках программирования непредсказуемо. В некоторых средах остаток может приобретать отрицательное значение, если исходное число было меньше нуля. Более того, отдельные языки программирования содержат сразу две разные встроенные операции — например, mod и double mod, выдающие отличающиеся результаты для одних и тех же цифр.
Вторая опасность кроется в схожести обозначений. Запись $a = b \bmod n$ и запись $a \equiv b \pmod n$ имеют принципиально разную семантику:
- В первом случае
mod— это инфиксная математическая функция (оператор), которая берет число $b$, делит его на $n$ и возвращает единственное конкретное значение остатка, которое затем сравнивается с $a$. - Во втором случае запись обозначает глобальное отношение эквивалентности между целыми мирами чисел $a$ и $b$ в рамках модульного пространства.
Чтобы минимизировать путаницу, Чепмен настоятельно рекомендует студентам использовать прозрачную запись через функцию $\text{rem}$ для вычисления остатков и знак тройного равенства ($\equiv$) для модульных сравнений, пока они не освоят предмет на экспертном уровне.
➕ Арифметические операции и правила подстановок 25:36
Главная ценность модульной арифметики раскрывается в упрощении комплексных вычислений. Проверенное временем школьное правило «четное плюс нечетное всегда дает нечетное» несет в себе глубокий смысл: какой бы огромный численный представитель конкретного класса ни был выбран, результат операции будет неизменным. Например, если взять любое число $a$, сравнимое с $3$ по модулю 5, и любое число $b$, сравнимое с $4$ по модулю 5, их сумма $a + b$ всегда будет сравнима с числом $7$, что в свою очередь эквивалентно базовому остатку $2 \pmod 5$.
Преподаватель формулирует фундаментальную теорему о правилах подстановки: если числа $a$ и $b$ эквивалентны по модулю $n$, то для любого целого числа $c$ справедливы следующие сравнения:
- $a + c \equiv b + c \pmod n$
- $a - c \equiv b - c \pmod n$
- $c - a \equiv c - b \pmod n$
- $a \times c \equiv b \times c \pmod n$
Это означает, что на любом промежуточном этапе сложения, вычитания или умножения исследователь имеет полное право заменить громоздкое число его компактным модульным остатком, не искажая итоговый результат вычислений.
Данное правило успешно масштабируется и на операцию возведения в степень: если основания равны ($a \equiv b \pmod n$), то и их степени будут эквивалентны ($a^c \equiv b^c \pmod n$) при условии положительного показателя $c$. Чепмен доказывает это утверждение методом математической индукции по показателю степени $c$:
- База индукции ($c = 1$): утверждение тривиально и верно, так как $a^1 = a$ и $b^1 = b$.
- Индукционный шаг: предполагая верность гипотезы для предыдущей степени ($a^{c-1} \equiv b^{c-1}$), мы анализируем выражение $a^c$. Его можно разложить на множители как $a^{c-1} \times a$. Опираясь на ранее доказанную теорему об умножении сравнений, мы последовательно заменяем первый множитель на $b^{c-1}$, а второй множитель — на $b$. В результате перемножения получаем $b^c$, что завершает доказательство индукционного перехода.
Важное предупреждение от лектора: Заменять основание степени в модульной арифметике можно сколько угодно, но заменять сам показатель степени категорически запрещено!
Попытка применить логику подстановки к показателю степени (предположив, что из $a \equiv b$ следует $c^a \equiv c^n$) является грубейшей математической ошибкой. В качестве сокрушительного контрпримера Чепмен предлагает рассмотреть поведение чисел по модулю 5. Число $1$ безусловно сравнимо с числом $6 \pmod 5$, однако если мы попробуем возвести отрицательную единицу в эти степени, то получим разные результаты: $(-1)^1 = -1$, в то время как $(-1)^6 = 1$. Поскольку $-1 \not\equiv 1 \pmod 5$, гипотеза о подстановке в показатель степени полностью проваливается.
🧮 Практикум: укрощение гигантских чисел 39:37
Для наглядной демонстрации мощи изученных правил подстановки Бринмор Чепмен разбирает на доске сложнейший демонстрационный пример. Требуется найти остаток от деления на 100 для следующего колоссального выражения:
$$x = 11335^{11111} \times 6 + 7799^{5000}$$
Попытка вычислить это число на обычном калькуляторе приведет к переполнению памяти, однако модульная арифметика позволяет решить задачу на доске за пару минут благодаря промежуточным сокращениям.
Пошаговый алгоритм решения выглядит следующим образом:
- Вычисление остатка при делении на 100 — это работа по модулю 100. Мы можем сразу упростить основание первого слагаемого, отбросив старшие разряды: $11335 \equiv 35 \pmod{100}$.
- Аналогично поступаем со вторым основанием: число $7799$ превращается в $99 \pmod{100}$. Но идти в вычисления с числом 99 неудобно. Лектор делает изящный шаг и заменяет 99 на эквивалентную ему отрицательную единицу, поскольку $99 \equiv -1 \pmod{100}$.
- Подставив $-1$ во второе слагаемое, мы получаем $(-1)^{5000}$. Отрицательная единица, возведенная в четную степень 5000, превращается в обычную $+1$. Все правое крыло исходного выражения теперь выглядит как $6 + 1 = 7$.
- Теперь нужно разобраться с левым крылом выражения: $35^{11111}$. Правил для сокращения показателей степеней у нас пока нет, поэтому Чепмен предлагает начать последовательно возводить число 35 в малые степени, чтобы нащупать закономерность.
- Считаем степени: $35^1 \equiv 35$. Квадрат числа $35^2 = 1225$, что по модулю 100 дает остаток $25$. Куб числа $35^3 = 35^2 \times 35 \equiv 25 \times 35 = 875$, что дает остаток $75$. Четвертая степень $35^4 = (35^2)^2 \equiv 25^2 = 625$, что снова возвращает нас к остатку $25$.
Перед глазами исследователей разворачивается строгий циклический паттерн: при возведении 35 в любую нечетную степень (выше первой) модульный остаток равен 75, а при возведении в любую четную степень остаток равен 25. Поскольку наш показатель степени $11111$ является нечетным числом, все выражение $35^{11111}$ по модулю 100 легитимно заменяется числом 75.
Финальный аккорд вычислений: умножаем полученные промежуточные результаты левого и правого крыла expressions: $75 \times 7 = 525$. Взяв остаток от деления 525 на 100, мы получаем окончательный ответ: 25.
Отвечая на вопросы студентов, Чепмен подтверждает, что при возведении в степень модульных чисел циклическое повторение остатков (паттерн) будет возникать абсолютно всегда. Логика здесь проста: по модулю 100 существует всего 100 возможных вариантов остатков. Если мы начнем возводить число в степень более 100 раз, значения неизбежно начнут сталкиваться и повторяться, образуя устойчивый период. В данном случае период повторения оказался очень коротким и удобным — он равен двум.
✖️ Проблема деления и мультипликативный инверс 50:38
Если со сложением, вычитанием и умножением в модульной арифметике нет никаких проблем, то операция деления таит в себе концептуальную опасность. Чтобы продемонстрировать это, Чепмен пишет на доске уравнение:
$$3x \equiv 3 \pmod 6$$
В рамках классической школьной алгебры над вещественными числами решение не вызывает вопросов: мы делим обе части уравнения на 3 и получаем ответ $x = 1$. Однако в модульном мире попытка бездумно сократить тройки приводит к потере правильных ответов. Преподаватель предлагает подставить в исходное выражение значение $x = 3$. Простые вычисления показывают: $3 \times 3 = 9$, а число 9 по модулю 6 имеет остаток 3. Уравнение сошлось, следовательно, $x = 3$ является абсолютно валидным решением. Но ведь число 3 не равно и не сравнимо с единицей по модулю 6. Таким образом, механически делить обе части модульного сравнения на общий коэффициент нельзя.
Корни этой проблемы кроются в том, что в модульной арифметике не существует дробных чисел в привычном понимании (вроде $1/3$). Вместо деления математики используют операцию умножения на специальное обратное число — мультипликативный инверс.
Мультипликативным инверсом числа $x$ по модулю $n$ (обозначается как $x^{-1}$) называется такое целое число, которое при перемножении с исходным $x$ дает единицу в рамках данного модуля:
$$x \times x^{-1} \equiv 1 \pmod n$$
Например, для числа 1 обратным элементом по любому модулю всегда будет являться сама единица. А для числа 3 по модулю 5 мультипликативным инверсом будет выступать число 2, поскольку их произведение $3 \times 2 = 6 \equiv 1 \pmod 5$.
Когда же существуют эти загадочные обратные элементы? Чепмен формулирует фундаментальную теорему: число $a$ имеет обратный элемент по модулю $n$ тогда и только тогда, когда числа $a$ и $n$ взаимно просты, то есть их наибольший общий делитель равен единице ($\gcd(a, n) = 1$).
Лектор объясняет это правило на пальцах: представьте, что $\gcd(a, n) = 2$, то есть оба числа четные. В таком случае, на какое бы целое число мы ни умножали четное $a$, на выходе мы всегда будем получать строго четный результат. А четное число никогда не сможет дать остаток 1 при делении на другое четное число $n$.
Строгое доказательство этой теоремы строится на базе тождества Безу. Запись $ab \equiv 1 \pmod n$ означает, что $n$ нацело делит разность $(ab - 1)$. Это можно переписать в виде уравнения с частным $q$:
$$qn = ab - 1$$
Перенесем единицу в одну сторону, а переменные в другую: $1 = ab - qn$. Перед нами не что иное, как целочисленная линейная комбинация чисел $a$ и $n$, равная единице. А как было повторено в самом начале лекции, линейная комбинация может равняться числу тогда и только тогда, когда это число делится на их $\gcd$. Поскольку единица делится только на единицу, их $\gcd(a, n)$ обязан быть равен 1.
Если условие взаимной простоты соблюдено, деление в модульных уравнениях становится полностью легитимным. Рассмотрим пример:
$$7x \equiv 14 \pmod{30}$$
Поскольку $\gcd(7, 30) = 1$, мы имеем полное право разделить обе части уравнения на 7 и заявить, что $x \equiv 2 \pmod{30}$. С академической точки зрения мы нашли обратный элемент для семерки по модулю 30 — это число 13 (так как $7 \times 13 = 91 \equiv 1 \pmod{30}$) — и умножили на него обе части уравнения, избавившись от коэффициента перед переменной.
👑 Малая теорема Ферма: укрощение показателей степеней 1:07:20
В финальной части лекции Бринмор Чепмен переходит к инструменту, который позволяет обойти ранее озвученный запрет на преобразования внутри показателей степеней. Этот инструмент — знаменитая Малая теорема Ферма. Преподаватель делает шутливое историческое отступление, призывая не путать ее с Великой теоремой Ферма. По мнению Чепмена, Великую теорему вообще не следовало приписывать Ферма, поскольку тот не оставил потомкам доказательства: «Он думал, что знает доказательство, но это был полный провал». Малая теорема Ферма — совсем другая история: она гораздо более элементарна, и ее авторство не вызывает сомнений.
Теорема гласит: если $p$ — простое число, а целое число $a$ не является кратным $p$ ($a \not\equiv 0 \pmod p$), то справедливо модульное равенство:
$$a^{p-1} \equiv 1 \pmod p$$
Значение этой теоремы трудно переоценить: если мы производим вычисления по строго простому модулю $p$, мы получаем законное право уменьшать (сокращать) показатели степеней, вычисляя их по модулю $p - 1$. Мы можем безболезненно отбрасывать любые степени, кратные числу $p-1$, поскольку они превращаются в единицу и не влияют на произведение.
Для доказательства Малой теоремы Ферма Чепмен предлагает исследовать специфическое множество чисел $S$, состоящее из элементов:
$$S = {a, 2a, 3a, \dots, (p-1)a}$$
Лектор утверждает, что если взять все элементы этого множества и вычислить их остатки по модулю $p$, то все полученные значения будут уникальными (различными) и среди них не окажется ни одного нуля. Отсутствие нулей очевидно: все коэффициенты перед $a$ строго меньше простого числа $p$, само $a$ не кратно $p$ по условию, а раз $p$ — простое число, то и произведение двух не кратных ему чисел не может делиться на него нацело.
Уникальность элементов доказывается методом от противного. Предположим, что два каких-то разных элемента множества выдали одинаковый остаток: $a \times i \equiv a \times j \pmod p$. Но поскольку $p$ — простое число, а $a$ не кратно ему, их $\gcd(a, p) = 1$. Это значит, что у числа $a$ существует обратный элемент, и мы имеем право сократить (разделить) обе части уравнения на $a$. На выходе получается, что коэффициент $i \equiv j \pmod p$. Но ведь наши коэффициенты изначально выбирались из диапазона от 1 до $p-1$, они физически не могут быть сравнимы по модулю $p$, если они не равны между собой. Мы пришли к противоречию, а значит, все элементы множества $S$ дают абсолютно разные остатки.
Поскольку у нас есть ровно $p-1$ элементов во множестве $S$, и они выдают $p-1$ уникальных ненулевых остатков, этот набор остатков должен в точности совпадать со стандартным эталонным набором остатков ${1, 2, 3, \dots, p-1}$, просто перемешанным в другом порядке.
Из этого логически вытекает, что если мы перемножим между собой все элементы множества $S$, то их произведение по модулю $p$ должно быть равно произведению всех элементов эталонного набора. Запишем это равенство:
$$(a) \times (2a) \times (3a) \times \dots \times ((p-1)a) \equiv 1 \times 2 \times 3 \times \dots \times (p-1) \pmod p$$
Вынесем все множители $a$ в левой части за скобки. Их там ровно $p-1$ штук. Внутри скобок останется обычное перемножение чисел от 1 до $p-1$, то есть факториал $(p-1)!$. Получаем выражение:
$$a^{p-1} \times (p-1)! \equiv (p-1)! \pmod p$$
Поскольку число $p$ простое, ни один из множителей внутри факториала $(p-1)!$ не делится на $p$, а значит, и сам факториал взаимно прост с модулем и имеет свой мультипликативный инверс. Мы со спокойной совестью сокращаем $(p-1)!$ в обеих частях уравнения и приходим к финальному тезису теоремы: $a^{p-1} \equiv 1 \pmod p$.
В качестве финального аккорда лекции Чепмен решает практическую задачу с использованием нового инструмента: нужно найти остаток от деления числа $7^{95}$ на простое число 13.
Поскольку модуль 13 является простым, мы можем применить Малую теорему Ферма и уменьшить показатель степени 95 по модулю $13 - 1 = 12$. Разделив 95 на 12, мы получаем остаток 11 ($95 = 12 \times 7 + 11$). Таким образом, исходная задача упрощается до вычисления выражения $7^{11} \pmod{13}$.
Чтобы не возводить семерку в 11-ю степень, Чепмен предлагает еще одно изящное модульное сокращение. Из теоремы Ферма известно, что $7^{12} \equiv 1 \pmod{13}$. Распишем это как $7^{11} \times 7 \equiv 1 \pmod{13}$. Перед нами формула поиска обратного элемента: выражение $7^{11}$ — это мультипликативный инверс для числа 7 по модулю 13. Нам остается лишь подобрать такое число, которое при умножении на 7 даст остаток 1 по модулю 13. Этим числом оказывается двойка, поскольку $7 \times 2 = 14 \equiv 1 \pmod{13}$. Задача решена, остаток равен 2.
