В лекции MIT OpenCourseWare профессор Эрик Демейн разбирает базовые концепции теории чисел — делимость и наибольший общий делитель (НОД). На примере знаменитой задачи с канистрами из кинофильма «Крепкий орешек 3» демонстрируется, как абстрактные алгебраические структуры помогают решать практические задачи и моделировать алгоритмы. Этот материал закладывает основу для понимания криптографии и систем исправления ошибок, используемых в современных технологиях связи.
📱 Роль теории чисел в современных технологиях и её история 0:00
Теория чисел традиционно изучает свойства целых чисел, обозначаемых символом $\mathbb{Z}$, включая положительные и отрицательные значения. Хотя долгое время эта дисциплина считалась исключительно абстрактной, сегодня она лежит в основе множества прикладных систем. Профессор Эрик Демейн отмечает, что аппарат теории чисел активно применяется в криптографии и системах исправления ошибок. Когда человек использует мобильный телефон, заходит в приложения онлайн-банкинга или передает данные по радиоволнам, программное обеспечение задействует математические алгоритмы для защиты и корректной передачи информации.
Эта наука имеет глубокие исторические корни:
- Вавилоняне занимались вопросами теории чисел еще 3800 лет назад.
- Пифагор и его последователи изучали свойства чисел около 2500 лет назад.
В прошлом веке знаменитый математик Годфри Харди, будучи убежденным пацифистом, утверждал, что теория чисел прекрасна своей абсолютной бесполезностью для военных нужд. По словам Харди, её удаленность от грубой человеческой деятельности позволяет ей оставаться «нежной и чистой». Однако в современную эпоху этот взгляд устарел, поскольку криптография стала неотъемлемой частью кибербезопасности и военных технологий.
🔢 Математическое определение делимости 2:01
Для обозначения делимости в математике используется вертикальная черта: выражение $a \mid b$ читается как «$a$ делит $b$» или «$b$ делится нацело на $a$». Формальное определение гласит: число $a$ делит $b$, если существует такое целое число $k$, при котором справедливо равенство:
$$b = k \cdot a$$
Важным нюансом является то, что определение строится через операцию умножения, а не деления. Это позволяет избежать неопределенности при работе с нулем. Если бы мы определяли делимость как требование, чтобы результат операции $b / a$ был целым числом, формула перестала бы работать при $a = 0$. В текущей формулировке свойство делимости корректно выполняется даже для нулевых делителей.
Из этого строгого определения вытекает несколько контринтуитивных следствий:
- Утверждение «$n$ — четное число» математически означает, что $2 \mid n$.
- Любое целое число делит свое отрицательное значение, то есть $-n \mid n$, так как коэффициент $k$ может быть равен $-1$.
- Абсолютно любое целое число делит 0, поскольку при $k = 0$ равенство $0 = 0 \cdot n$ всегда остается верным.
- Число 0 является четным, так как оно делится на 2 без остатка.
🛠️ Общие делители и целочисленные линейные комбинации 5:37
Если число $d$ одновременно делит целые числа $a$ и $b$, оно называется их общим делителем. Свойства делимости позволяют утверждать, что в таком случае $d$ также разделит их сумму: $d \mid (a + b)$. Доказать это просто: если представить $a = j \cdot d$ и $b = k \cdot d$, то их сумма будет равна $(j + k) \cdot d$, где сумма коэффициентов также является целым числом.
Более общее правило гласит, что $d$ делит любое выражение вида:
$$s \cdot a + t \cdot b$$
Здесь $s$ и $t$ — произвольные целые числа. Структура подобного вида называется целочисленной линейной комбинацией (ЦЛК). Эрик Демейн вводит для неё аббревиатуру ILC (Integer Linear Combination) для экономии времени при записях на доске. По сути, это аналог линейной комбинации из линейной алгебры, но с жестким ограничением: все коэффициенты обязаны быть строго целыми.
Профессор указывает на любопытную взаимосвязь: обычная делимость — это линейная комбинация всего одного числа, показывающая, что $b$ конструируется исключительно из $a$. Однако настоящую математическую интригу и практическую пользу представляют комбинации двух и более чисел.
🎬 Головоломка с канистрами: как спасти Манхэттен 8:50
Для демонстрации силы целочисленных линейных комбинаций Эрик Демейн обращается к классической задаче о переливании воды, которая стала всемирно известной благодаря блокбастеру «Крепкий орешек 3: Возмездие». По сюжету, главные герои Джон Маклейн и Зевс вынуждены разгадывать изощренные загадки террориста Саймона, чтобы предотвратить разрушительный взрыв в центре Нью-Йорка.
Условия кинематографической задачи следующие:
- Имеются две канистры емкостью 5 и 3 галлонов.
- Доступен неограниченный источник воды (городской фонтан).
- Необходимо отмерить ровно 4 галлона воды и поместить их в большую канистру.
Эту задачу можно формализовать с помощью теории конечных автоматов, где состояние системы описывается парой чисел $(x, y)$ — текущим объемом воды в первой и второй канистрах соответственно. Начальное состояние автомата — $(0, 0)$. Цель игроков — перевести автомат в терминальное состояние $(4, y)$.
🔄 Пространство состояний и инвариант неразрешимости 11:54
В рамках данной модели автомата разрешены следующие типы переходов:
- Полное заполнение любой канистры из фонтана — переход в состояние $(a, y)$ или $(x, b)$.
- Полное опустошение канистры на землю — переход в состояние $(0, y)$ или $(x, 0)$.
- Переливание воды из одной емкости в другую до тех пор, пока первая не опустеет или вторая не заполнится до краев.
Для канистр объемом 5 и 3 галлонов пошаговое решение выглядит так: сначала полностью заполняется 5-галлоновая канистра, затем из неё отливают 3 галлона в меньшую емкость. В большой канистре остается ровно 2 галлона. Маленькую канистру опустошают, переливают туда оставшиеся 2 галлона, снова наполняют большую канистру до 5 галлонов и аккуратно доливают из неё 1 галлон в маленькую до её полного заполнения. В итоге в большой канистре остается ровно 4 галлона. Террорист побежден, Манхэттен спасен.
Однако, если изменить условия и взять канистры емкостью 6 и 4 галлонов, поставив целью получение 3 галлонов, задача становится абсолютно неразрешимой. Профессор объясняет эту неудачу через принцип инвариантов.
Ключевая лемма гласит:
Все достижимые объемы воды в канистрах в любой момент времени являются целочисленными линейными комбинациями их исходных емкостей $a$ и $b$.
Базовый случай тривиален: начальное состояние $(0, 0)$ представимо как $0 \cdot a + 0 \cdot b$. Индуктивный шаг показывает, что любые разрешенные операции переливания лишь складывают или вычитают емкости $a$ и $b$, сохраняя свойство линейной комбинации,. Поскольку числа 6 и 4 четные, любой их общий делитель (в данном случае 2) должен делить и любой итоговый объем. Но число 2 не делит нечетную тройку, что строго доказывает невозможность решения данной модификации головоломки.
⚖️ Два эквивалентных определения НОД 26:36
Поиск ответа на вопрос, можно ли выразить целевой объем через емкости сосудов, неизбежно приводит к понятию наибольшего общего делителя (Greatest Common Divisor, GCD). Англоязычный термин восходит к британской математической традиции, где слово great используется в значении «крупный, большой». Эрик Демейн предлагает рассмотреть два эквивалентных определения НОД.
Первое определение, основанное на поиске максимума:
НОД чисел $a$ и $b$ — это наибольшее целое число $d$, которое одновременно делит и $a$, и $b$.
У этого интуитивного определения есть одно тонкое исключение: для пары $(0, 0)$ не существует максимального делителя, так как ноль делится на абсолютно любое целое число. Поэтому математически принимается, что $\text{GCD}(0, 0) = 0$.
Второе определение, сформулированное через отношение делимости:
НОД — это единственный неотрицательный общий делитель чисел $a$ и $b$, который без остатка делится на любой другой их общий делитель.
Например, для чисел 4 и 6 общими делителями являются $\pm 2$ и $\pm 1$. Число 2 является наибольшим среди них и одновременно делится на все остальные делители из этого подмножества. Другой важный частный случай: $\text{GCD}(0, b) = |b|$. Поскольку любое число делит ноль, наибольшим общим делителем нуля и некоторого целого числа $b$ будет являться абсолютное значение самого $b$.
📉 Вычитание против деления: эволюция алгоритмов НОД 33:35
Для вычисления НОД больших чисел необходим эффективный алгоритм. Простейший и самый древний подход опирается на операцию вычитания. Лемма о вычитании утверждает, что $\text{GCD}(a, b) = \text{GCD}(a - b, b)$. Профессор доказывает это утверждение через равенство множеств: множество общих делителей пары $(a, b)$ в точности совпадает со множеством общих делителей пары $(a - b, b)$. Доказательство проводится классическим методом — через демонстрацию взаимного включения этих двух множеств друг в друга,.
Используя свойство симметрии ($\text{GCD}(a, b) = \text{GCD}(b, a)$), можно построить пошаговый алгоритм последовательного вычитания меньшего числа из большего. Например, для пары $(9, 6)$ шаги вычислений будут следующими:
$$\text{GCD}(9, 6) = \text{GCD}(3, 6) = \text{GCD}(3, 3) = \text{GCD}(3, 0) = 3$$-.
Однако у этого алгоритма крайне низкая скорость работы в худших сценариях. Потребуется ровно 100 шагов последовательного вычитания, чтобы найти $\text{GCD}(1, 100)$. Временная сложность такого алгоритма пропорциональна величине самих чисел и укладывается в рамки Bounds $O(a + b)$. Для современных 100-битных чисел, масштаб которых сопоставим с количеством частиц в известной нам Вселенной ($2^{100}$), подобный подход абсолютно неприменим.
Решением этой проблемы становится фундаментальная теорема о делении с остатком. Согласно ей, для любого целого числа $n$ и положительного делителя $d$ существует единственная пара целых чисел — частное $q$ (обозначаемое как div) и остаток $r$ (обозначаемый как rem), удовлетворяющая условию:
$$n = q \cdot d + r, \quad 0 \le r < d$$
⚡ Алгоритм Евклида и его экспоненциальное ускорение 50:51
Замена последовательного вычитания делением с остатком кардинально меняет скорость вычислений. Новая теорема утверждает: $\text{GCD}(a, b) = \text{GCD}(b, a \text{ rem } b)$. В этом случае вместо длинной цепочки вычитаний мы сразу получаем остаток. Так, для пары $(100, 1)$ алгоритм находит верный ответ всего за один шаг деления: $\text{GCD}(100, 1) = \text{GCD}(1, 0) = 1$.
Этот метод, известный как алгоритм Евклида, был описан в древнегреческой литературе около 300 года до н.э.. Его работу можно наглядно представить в виде конечного автомата со следующими правилами переходов:
$$(x, y) \to (y, x \text{ rem } y)$$
Если текущее значение правого аргумента $y = 0$, автомат останавливается и возвращает левый аргумент $x$ в качестве итогового результата.
Профессор Демейн доказывает завершаемость этого алгоритма двумя способами. Простой способ — функция суммы аргументов $x + y$ строго уменьшается на каждом шаге. Однако более глубокий анализ показывает, что количество бит в двоичной записи чисел также строго снижается. Поскольку остаток от деления всегда меньше половины исходного числа ($x \text{ rem } y < x/2$), на каждом шаге гарантированно отсекается как минимум один бит информации.
Это обеспечивает экспоненциальное ускорение алгоритма:
- Вместо медленной линейной сложности $O(a + b)$ мы получаем временную сложность $O(\log a + \log b)$.
- Для двух огромных 100-битных чисел алгоритм Евклида потребует всего около 100 операций вместо астрономических $2^{100}$ шагов вычитания.
Геометрически работу алгоритма Евклида можно представить как замощение большого прямоугольника со сторонами $a$ и $b$ квадратами со стороной $b$. Оставшийся незамощенным прямоугольник меньшего размера имеет стороны $b$ и $a \text{ rem } b$, и процесс рекурсивно повторяется до тех пор, пока вся фигура не замостится идеально.
🧪 Лемма Безу и древнеиндийский «Измельчитель» 1:07:56
Заключительная часть лекции связывает алгоритм Евклида с линейными комбинациями через лемму Безу. Она утверждает, что НОД двух чисел всегда можно представить в виде их целочисленной линейной комбинации. Исторически Этьен Безу опубликовал эту лемму в 1779 году, однако задолго до него её открыл французский математик Клод Баше де Мезириак в 1624 году, а еще раньше — индийские математики около 500 года н.э..
Доказательство леммы строится по принципу сильной индукции на основе шагов алгоритма Евклида-. На базе этого математического доказательства возникает Расширенный алгоритм Евклида, который в древней Индии называли «Куттака» (Kuttaka), что в переводе с санскрита означает «Измельчитель» (The Pulverizer). Этот алгоритм был подробно описан выдающимся математиком Ариабхатой около 500 года н.э..
«Измельчитель» не просто находит наибольший общий делитель, но и параллельно вычисляет коэффициенты $s$ и $t$ для искомой линейной комбинации. На каждом шаге автомат отслеживает уравнения для обоих аргументов. Для канистр из кинофильма емкостью 5 и 3 галлона работа алгоритма дает следующее точное выражение:
$$1 = -1 \cdot 5 + 2 \cdot 3$$
Чтобы получить требуемые для спасения Нью-Йорка 4 галлона, достаточно умножить обе части этого уравнения на 4:
$$4 = -4 \cdot 5 + 8 \cdot 3$$
Данное уравнение служит прямой и понятной инструкцией к действию: нужно ровно 8 раз наполнить 3-галлоновую канистру и перелить воду в 5-галлоновую, полностью опустошая последнюю на землю каждый раз, когда она переполняется (всего 4 раза). В результате этих несложных манипуляций в канистре останется ровно 4 галлона воды, что и позволило киногероям успешно обезвредить бомбу террористов.
