Натуральные числа: от счёта до глубин теории чисел

§ 1. Три вопроса без предупреждения

Запишите ответы на листке — не обсуждая с соседом.

1. Сколько натуральных чисел? Напишите конкретный ответ.
2. Является ли число \(1\) простым? Да или нет — и почему.
3. Верно ли утверждение: «Каждое чётное число больше \(2\) является суммой двух простых»? Проверьте числа \(20\), \(30\), \(100\). Удастся ли найти контрпример?

На первый вопрос у каждого есть ответ. На второй — большинство ошибаются. Третий вопрос не решён никем на Земле уже почти три века.

Добро пожаловать в теорию чисел.

§ 2. Зачем считать и почему это оказалось сложно

Человек считает раньше, чем говорит. Кость Ишанго, найденная в Конго и датируемая примерно \(20\,000\) лет назад, хранит группы насечек — одно из древнейших свидетельств счёта. Натуральные числа рождаются из простейшей потребности: сколько мамонтов, сколько дней, сколько воинов. Счёт предшествует письменности и предшествует земледелию.

Но то, что началось как метки на кости, превратилось в одну из самых глубоких областей математики — теорию чисел. Гаусс называл её «королевой математики». Это не случайный комплимент: именно здесь ставятся вопросы, понять которые может школьник, а ответить на них не смогли лучшие математики мира.

Исторический путь: от насечек до аксиом

Египтяне около \(3000\) года до н. э. использовали натуральные числа для измерения площадей при восстановлении полей после разлива Нила. Вавилоняне около \(2000\) года до н. э. разработали позиционную систему счисления с основанием \(60\) — именно поэтому мы делим час на \(60\) минут, а окружность на \(360\) градусов.

Пифагорейцы в VI веке до н. э. объявили числа основой мироздания. «Всё есть число» — их девиз. Они изучали совершенные числа, дружественные числа и другие структуры, которые сначала кажутся игрой ума, но позже оказываются важными для алгебры и теории чисел. Например, число \(6\) совершенно, потому что

\[ 6=1+2+3. \]

Евклид около \(300\) года до н. э. в «Началах» систематически изложил теорию делимости и простых чисел. Он доказал бесконечность простых — аргументом, который остаётся одним из красивейших доказательств в истории математики.

Прошли тысячелетия счёта и вычислений, прежде чем математики задали вопрос, который сейчас кажется странным: а что такое вообще натуральное число? Откуда оно берётся? Ответ дал итальянский математик Джузеппе Пеано в \(1889\) году — через систему аксиом. До этого многие арифметические истины считались просто «очевидными».

Ключевая идея главы проста и неожиданна: натуральные числа — не только школьный счёт \(1,2,3,4,\ldots\). Это фундамент арифметики, алгоритмов, криптографии и нерешённых задач современной науки.

В этой главе мы пройдём путь от аксиом Пеано до алгоритма Евклида, от признаков делимости до RSA, от простых чисел до гипотезы Гольдбаха. Мы увидим, что за внешней простотой натурального ряда скрывается глубина, которая до сих пор не исчерпана.

§ 3. Что такое \(\mathbb{N}\)

Прежде чем изучать свойства натуральных чисел, нужно договориться: что именно мы изучаем.

В российской школьной традиции натуральными числами называют числа

\[ 1,2,3,4,\ldots \]

то есть положительные целые числа. Обозначение:

\[ \mathbb{N}=\{1,2,3,4,\ldots\}. \]

По международному стандарту ISO \(80000\)-\(2\), принятому во многих университетских курсах и в программировании, множество натуральных чисел часто записывают как

\[ \mathbb{N}=\{0,1,2,3,\ldots\}. \]

Тогда для натуральных чисел без нуля используют обозначения \(\mathbb{N}^{*}\) или \(\mathbb{N}^{+}\).

В этой главе мы будем явно указывать, когда включение нуля принципиально важно. Это не мелочь: от выбора соглашения зависит, есть ли у натурального ряда первый элемент \(0\) или \(1\), как формулируются аксиомы и как записываются некоторые алгоритмы.

Бесконечность натуральных чисел

Натуральных чисел бесконечно много. Это звучит очевидно, но что значит «бесконечно» строго? Учебная версия доказательства выглядит так.

Предположим противное: пусть натуральных чисел конечное число, и самое большое из них равно \(N\). Рассмотрим число \(N+1\). Оно тоже натуральное, потому что мы всегда можем прибавить единицу, и при этом оно больше \(N\). Получили противоречие.

Значит, никакого наибольшего натурального числа не существует. Натуральный ряд не заканчивается.

Строгое обоснование этой идеи требует аксиомы преемника, которую мы введём в следующем параграфе. Но уже сейчас видна главная мысль: натуральные числа порождаются операцией «перейти к следующему», и эту операцию можно применять сколько угодно раз.

Мощность множества \(\mathbb{N}\) называется счётной бесконечностью и обозначается \(\aleph_0\) — «алеф-ноль». Удивительно, но множество чётных натуральных чисел

\[ \{2,4,6,8,\ldots\} \]

имеет ту же мощность, что и всё \(\mathbb{N}\). Каждому натуральному числу \(n\) можно сопоставить чётное число \(2n\). Ни одно чётное число не потеряется, и ни одно натуральное число не останется без пары.

Это парадокс Галилея: часть бесконечного множества может быть «такой же большой», как всё множество. Бесконечность ломает привычную конечную интуицию.

Натуральные числа и счёт

Фундаментальная связь такова: натуральные числа кодируют количество элементов конечного множества. Именно поэтому они стали универсальным языком описания мира: количество яблок, возраст, число шагов алгоритма, размер массива в программе.

В информатике типы данных int, long, byte — это целые числа в конечном диапазоне. В основе работы процессора лежит арифметика целых чисел, реализованная в кремниевых транзисторах. Натуральные числа — не только абстракция учебника, но и фундамент машинной арифметики.

§ 4. Аксиомы Пеано: строительный чертёж арифметики

Школьная интуиция работает прекрасно: мы складываем, умножаем, сравниваем числа, не думая о фундаменте. Но математике этого мало. Без явного набора базовых правил нельзя строго вывести арифметику и нельзя понять, какие свойства действительно являются следствиями, а какие мы просто привыкли считать очевидными.

Аксиомы Пеано — это контракт: вот всё, что мы принимаем без доказательства. Всё остальное должно быть выведено. Этот контракт настолько строг, что из нескольких коротких правил строится вся классическая арифметика, включая сложение, умножение и индукцию.

Джузеппе Пеано (\(1858\)–\(1932\)) — итальянский математик и логик, профессор Туринского университета. Помимо аксиом натуральных чисел, он разработал математическую нотацию, часть которой используется до сих пор. Например, символ \(\in\) для принадлежности элементу множеству ввёл именно Пеано.

Аксиомы натуральных чисел появились в его работе Arithmetices principia, nova methodo exposita. Это один из важных документов в истории математики: арифметика впервые была описана не как набор очевидностей, а как формальная система.

Пять аксиом

Аксиомы Пеано определяют натуральные числа через два понятия: начальный элемент и операцию преемника. Преемник числа \(n\) обозначают \(S(n)\); интуитивно это «следующее число после \(n\)».

В версии, где натуральный ряд начинается с \(1\), аксиомы можно записать так.

1. Существует натуральное число \(1\).
2. Для каждого натурального числа \(n\) существует единственное натуральное число \(S(n)\) — его преемник.
3. Число \(1\) не является преемником никакого натурального числа.
4. Если \(S(m)=S(n)\), то \(m=n\).
5. Если утверждение \(P\) истинно для \(1\), и из истинности \(P(n)\) следует истинность \(P(S(n))\), то \(P\) истинно для всех натуральных чисел.

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

Как из аксиом рождается сложение

Сложение определяется рекурсивно через преемник:

\[ a+1:=S(a), \]

\[ a+S(b):=S(a+b). \]

Первая строка говорит: прибавить единицу — значит перейти к следующему числу. Вторая строка говорит: прибавить «следующее после \(b\)» — значит сначала прибавить \(b\), а потом взять преемник результата.

Умножение определяется аналогично:

\[ a\cdot 1:=a, \]

\[ a\cdot S(b):=a\cdot b+a. \]

Из этих определений и аксиом Пеано выводятся знакомые свойства арифметики: коммутативность, ассоциативность, дистрибутивность. То, что в школе выглядит как очевидная таблица, в строгой математике имеет фундамент.

§ 5. Математическая индукция

Индукция — один из мощнейших инструментов математика. Представьте бесконечный ряд костяшек домино, пронумерованных \(1,2,3,\ldots\). Известно два факта: первая костяшка падает, а каждая упавшая костяшка толкает следующую. Тогда упадут все.

В математике «падение» — это истинность утверждения \(P(n)\). База индукции доказывает \(P(1)\). Индукционный переход доказывает, что из \(P(n)\) следует \(P(n+1)\). После этого принцип индукции позволяет заключить: утверждение верно для всех натуральных \(n\).

Структура доказательства всегда одна и та же. Сначала база. Потом предположение индукции. Затем переход. И только после этого — вывод для всех натуральных чисел.

Индукция — не только метод доказательства, но и логическая структура. К её логической сути — связи с правилами вывода, с отрицанием кванторов, с принципом наименьшего элемента — мы вернёмся в главе о множествах и логике.

Пример: сумма первых \(n\) натуральных чисел

Докажем формулу

\[ 1+2+3+\ldots+n=\frac{n(n+1)}{2} \]

для всех \(n\in\mathbb{N}\).

База: при \(n=1\) левая часть равна \(1\), правая часть равна

\[ \frac{1\cdot 2}{2}=1. \]

Переход: предположим, что для некоторого \(n\) верно

\[ 1+2+\ldots+n=\frac{n(n+1)}{2}. \]

Докажем формулу для \(n+1\):

\[ 1+2+\ldots+n+(n+1)=\frac{n(n+1)}{2}+(n+1). \]

Вынесем \(n+1\):

\[ \frac{n(n+1)}{2}+(n+1)=(n+1)\left(\frac{n}{2}+1\right)=\frac{(n+1)(n+2)}{2}. \]

Это та же формула, но с \(n+1\) вместо \(n\). Доказательство завершено.

При \(n=100\) получаем

\[ \frac{100\cdot 101}{2}=5050. \]

Именно этот ответ, по легенде, быстро нашёл десятилетний Гаусс.

Учитель Бюттнер задал классу сложить все числа от \(1\) до \(100\) и рассчитывал, что дети будут заняты надолго. Карл Фридрих Гаусс заметил, что

\[ 1+100=101, \]

\[ 2+99=101, \]

\[ 3+98=101. \]

Таких пар ровно \(50\), значит сумма равна \(50\cdot 101=5050\). По сути, Гаусс увидел структуру там, где остальные видели длинную арифметику.

Задача для читателя. Докажите по индукции, что сумма первых \(n\) нечётных чисел равна \(n^2\):

\[ 1+3+5+\ldots+(2n-1)=n^2. \]

Подсказка: нечётные числа имеют вид \(2k-1\) для \(k=1,2,3,\ldots\).

§ 6. Арифметические операции: законы и границы

Сложение и умножение натуральных чисел наследуют все законы, которые вы знаете. Но знать закон и понимать, почему он выполняется, — разные вещи.

Для сложения верны:

\[ a+b=b+a, \]

\[ (a+b)+c=a+(b+c), \]

и закон сокращения: если \(a+c=b+c\), то \(a=b\).

Для умножения верны:

\[ a\cdot b=b\cdot a, \]

\[ (a\cdot b)\cdot c=a\cdot (b\cdot c), \]

\[ a\cdot 1=a, \]

\[ a\cdot(b+c)=a\cdot b+a\cdot c. \]

Кроме того, натуральные числа замкнуты относительно сложения и умножения:

\[ a+b\in\mathbb{N},\qquad a\cdot b\in\mathbb{N}. \]

Коммутативность сложения не так очевидна, как кажется. В строгом построении её доказывают по индукции: сначала устанавливают \(a+1=1+a\), затем переходят к \(a+S(b)=S(b)+a\). То, что выглядит «само собой», оказывается теоремой.

Почему вычитание и деление «ломаются»

Натуральные числа не замкнуты относительно вычитания и деления. Это фундаментальное ограничение, а не недостаток.

Например, \(3-5\) не является натуральным числом. Именно поэтому математики расширили \(\mathbb{N}\) до \(\mathbb{Z}\) — множества целых чисел, добавив отрицательные числа.

Деление тоже выходит за пределы натуральных чисел: \(7\div 3\) не является натуральным числом. Поэтому появляется множество рациональных чисел \(\mathbb{Q}\).

Каждое расширение числовой системы — это ответ на вопрос: какие операции мы хотим выполнять без ограничений?

Программисты сталкиваются с этой идеей каждый день. Тип uint8 хранит беззнаковые \(8\)-битные целые числа от \(0\) до \(255\). Попытка записать \(256\) приводит к переполнению:

\[ 255+1=0. \]

Это не «ошибка компьютера», а арифметика по модулю \(256\) — арифметика остатков. Натуральные числа в математике бесконечны, но числа в памяти компьютера всегда живут в конечном диапазоне.

Порядок и принцип наименьшего элемента

Натуральные числа не только складываются и умножаются — они упорядочены. Отношение \(<\) обладает свойствами: число не меньше самого себя, из \(a<b\) и \(b<c\) следует \(a<c\), а для любых \(a\) и \(b\) верно ровно одно из трёх: \(a<b\), \(a=b\), \(a>b\).

Ключевая теорема:

\[ \text{каждое непустое подмножество } \mathbb{N} \text{ содержит наименьший элемент.} \]

Формально: если \(A\subseteq\mathbb{N}\) и \(A\ne\varnothing\), то существует \(m\in A\) такое, что

\[ m\le a \]

для всех \(a\in A\).

Этот принцип эквивалентен математической индукции: они выводятся друг из друга. Именно на нём основан метод бесконечного спуска Ферма.

Пьер де Ферма (\(1607\)–\(1665\)) использовал мощную технику доказательства. Идея такова: предположим, что утверждение ложно для некоторого натурального числа \(n\). Покажем, что тогда оно ложно и для некоторого \(m<n\). Потом — для ещё меньшего числа. Получается бесконечная убывающая цепочка натуральных чисел.

Но такая цепочка невозможна: у любого непустого множества натуральных чисел есть наименьший элемент. Значит, исходное предположение было неверным.

Ферма применял этот метод, чтобы доказать, что уравнение

\[ x^4+y^4=z^2 \]

не имеет решений в натуральных числах. Это единственный случай Великой теоремы Ферма, который доказал сам Ферма.

§ 7. Делимость и деление с остатком

Делимость — центральное отношение теории чисел. Оно кажется простым, но именно через него строятся простые числа, НОД, алгоритм Евклида, сравнения по модулю и криптография.

Натуральное число \(a\) делится на натуральное число \(b\), если существует натуральное число \(k\) такое, что

\[ a=b\cdot k. \]

Пишут \(b\mid a\). Число \(b\) называется делителем числа \(a\), а \(a\) — кратным числа \(b\).

Например,

\[ 6\mid 24, \]

потому что \(24=6\cdot 4\). Но

\[ 5\nmid 24, \]

потому что нет натурального \(k\), при котором \(24=5k\).

Для любых натуральных чисел \(a\) и \(b\), где \(b>0\), существуют единственные числа \(q\) и \(r\) такие, что

\[ a=bq+r, \]

где

\[ 0\le r<b. \]

Число \(q\) называется частным, число \(r\) — остатком. Если \(r=0\), то \(a\) делится на \(b\).

Остаток от деления на \(m\) — основа модульной арифметики. Запись

\[ a\equiv r\pmod m \]

означает: числа \(a\) и \(r\) дают одинаковый остаток при делении на \(m\).

Признаки делимости: единая логика

Признаки делимости — не набор заклинаний. Все они следуют из одной идеи: в десятичной записи числа

\[ n=d_k\cdot 10^k+d_{k-1}\cdot 10^{k-1}+\ldots+d_1\cdot 10+d_0 \]

остаток от деления на \(m\) определяется остатками степеней \(10\) по модулю \(m\).

Общая формула:

\[ n\equiv d_k(10^k\bmod m)+\ldots+d_1(10\bmod m)+d_0\pmod m. \]

Если \(10\equiv 0\pmod m\), мы смотрим последние цифры. Так работают признаки делимости на \(2\), \(4\), \(5\), \(8\), \(10\).

Если \(10\equiv 1\pmod m\), работает сумма цифр. Так устроены признаки на \(3\) и \(9\).

Если \(10\equiv -1\pmod m\), работает чередующаяся сумма. Так устроен признак делимости на \(11\).

Проверим число \(123\,456\,789\).

Сумма цифр равна

\[ 1+2+3+4+5+6+7+8+9=45. \]

Число \(45\) делится на \(9\) и на \(3\), значит \(123\,456\,789\) делится на \(9\) и на \(3\).

Чередующаяся сумма для признака делимости на \(11\):

\[ 9-8+7-6+5-4+3-2+1=5. \]

Число \(5\) не делится на \(11\), значит исходное число на \(11\) не делится.

Сравнения по модулю можно складывать и умножать. Если

\[ a\equiv b\pmod m, \]

и

\[ c\equiv d\pmod m, \]

то

\[ a+c\equiv b+d\pmod m, \]

и

\[ ac\equiv bd\pmod m. \]

Это превращает остатки в полноценную арифметическую систему — кольцо \(\mathbb{Z}/m\mathbb{Z}\), важное для криптографии.

Задачи к параграфу.

Базовая. Придумайте число, которое делится на \(2\), \(3\), \(4\), \(5\) и \(6\) одновременно. Какое наименьшее такое число?

Аналитическая. Докажите: если \(a\equiv b\pmod m\) и \(c\equiv d\pmod m\), то \(ac\equiv bd\pmod m\).

Исследовательская. Создайте программу на Python, которая для заданного числа проверяет делимость на все \(m\) от \(2\) до \(12\) и выводит результат.

§ 8. Простые числа: атомы арифметики

Если натуральные числа — это молекулы, то простые числа — атомы. Как в химии атомы не разлагаются на более простые элементы, простые числа не раскладываются в произведение меньших натуральных чисел, кроме тривиального умножения на \(1\).

Натуральное число \(p>1\) называется простым, если оно имеет ровно два натуральных делителя: \(1\) и \(p\).

Натуральное число \(n>1\), не являющееся простым, называется составным. Оно имеет хотя бы один делитель, отличный от \(1\) и \(n\).

Число \(1\) не является ни простым, ни составным. Это особый случай.

Первые простые числа:

\[ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\ldots \]

Почему \(1\) не простое — это не придирка. Если считать \(1\) простым, разложение на простые множители перестанет быть единственным:

\[ 12=2^2\cdot 3, \]

но тогда можно было бы писать и так:

\[ 12=1\cdot 2^2\cdot 3=1^2\cdot 2^2\cdot 3=1^3\cdot 2^2\cdot 3. \]

Основная теорема арифметики ломается. Исключение \(1\) из простых чисел нужно не для красоты определения, а для единственности разложения.

Решето Эратосфена

Решето Эратосфена — древний алгоритм нахождения простых чисел до заданного предела \(N\).

Для чисел до \(50\) алгоритм работает так:

1. Выписать все числа от \(2\) до \(50\).
2. Взять первое незачёркнутое число \(2\) и зачеркнуть все его кратные: \(4,6,8,\ldots\).
3. Взять следующее незачёркнутое число \(3\) и зачеркнуть его кратные: \(6,9,12,\ldots\).
4. Продолжать до числа \(\sqrt{50}\approx 7{,}07\).

Оставшиеся незачёркнутые числа — простые:

\[ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47. \]

Почему достаточно идти только до \(\sqrt{N}\)? Если число \(n\le N\) составное, то у него есть делитель, не превосходящий \(\sqrt{n}\). Иначе произведение двух делителей было бы больше \(n\).

Теорема Евклида: простых чисел бесконечно много

Предположим противное: простых чисел конечное число, и все они перечислены:

\[ p_1,p_2,\ldots,p_n. \]

Рассмотрим число

\[ N=p_1p_2\ldots p_n+1. \]

При делении \(N\) на любое \(p_i\) остаток равен \(1\), потому что произведение \(p_1p_2\ldots p_n\) делится на \(p_i\), а добавленная единица — нет.

Значит, ни одно из чисел \(p_1,\ldots,p_n\) не делит \(N\). Но \(N\) либо само простое, либо имеет простой делитель. В любом случае существует простое число, которого не было в исходном списке. Противоречие.

Следовательно, простых чисел бесконечно много.

Интересный факт. Самое большое известное простое число на момент подготовки этой версии главы —

\[ 2^{136\,279\,841}-1. \]

У него \(41\,024\,320\) десятичных цифр. Оно было найдено в рамках проекта GIMPS, Great Internet Mersenne Prime Search. Простые числа вида

\[ 2^p-1 \]

называются простыми Мерсенна.

§ 9. Основная теорема арифметики

Если простые числа — атомы арифметики, то естественный вопрос звучит так: однозначно ли любое число собирается из этих атомов?

Основная теорема арифметики отвечает: да.

Каждое натуральное число \(n>1\) может быть представлено в виде произведения простых чисел:

\[ n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}, \]

где \(p_1<p_2<\ldots<p_k\) — простые числа, а \(\alpha_i\ge 1\) — натуральные показатели. Это представление единственно с точностью до порядка множителей.

Примеры:

\[ 12=2^2\cdot 3, \]

\[ 360=2^3\cdot 3^2\cdot 5, \]

\[ 1001=7\cdot 11\cdot 13, \]

\[ 997=997, \]

\[ 1\,000\,000=2^6\cdot 5^6. \]

Существование разложения следует из определения составного числа. Если число составное, у него есть делитель \(d\), где \(1<d<n\). Тогда и \(d\), и \(n/d\) можно разлагать дальше. Процесс не может продолжаться бесконечно: на каждом шаге числа уменьшаются, а убывающая последовательность натуральных чисел конечна.

Единственность глубже. Почему нельзя получить два разных разложения? Здесь нужна лемма Евклида:

если простое число \(p\) делит произведение \(ab\), то \(p\) делит \(a\) или \(p\) делит \(b\).

Именно эта лемма делает простые числа «атомами». Простое число не может незаметно появиться внутри произведения: если оно делит произведение, оно делит один из множителей.

НОД и НОК через канонические разложения

Пусть

\[ a=2^3\cdot 3^2\cdot 5, \]

а

\[ b=2\cdot 3^3\cdot 7. \]

НОД берёт общие простые множители в минимальных степенях:

\[ \gcd(a,b)=2^1\cdot 3^2=18. \]

НОК берёт все простые множители в максимальных степенях:

\[ \operatorname{lcm}(a,b)=2^3\cdot 3^3\cdot 5\cdot 7=7560. \]

Связь между ними:

\[ \gcd(a,b)\cdot \operatorname{lcm}(a,b)=a\cdot b. \]

Проверка:

\[ 18\cdot 7560=136\,080=360\cdot 378. \]

§ 10. Алгоритм Евклида

Алгоритм Евклида — один из старейших известных алгоритмов. Он описан в «Началах» Евклида около \(300\) года до н. э. и до сих пор остаётся стандартным способом вычисления НОД. Его используют в криптографии, компиляторах и компьютерной алгебре.

Идея алгоритма:

\[ \gcd(a,b)=\gcd(b,r), \]

где \(r\) — остаток от деления \(a\) на \(b\).

Повторяем деление с остатком, пока остаток не станет нулём. Последний ненулевой остаток — это НОД.

Пример: найдём \(\gcd(252,105)\).

\[ 252=105\cdot 2+42, \]

\[ 105=42\cdot 2+21, \]

\[ 42=21\cdot 2+0. \]

Остаток стал нулём. Последний ненулевой остаток равен \(21\), значит

\[ \gcd(252,105)=21. \]

Проверка:

\[ 252=21\cdot 12, \]

\[ 105=21\cdot 5. \]

В Python алгоритм Евклида занимает несколько строк:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(252, 105))  # 21

Что демонстрирует этот код? Древний алгоритм в современной записи. Математическая идея превращается в цикл, остаток % управляет переходом, а последний ненулевой остаток становится ответом.

Тождество Безу

Из алгоритма Евклида следует поразительный результат: для любых натуральных \(a\) и \(b\) существуют целые числа \(s\) и \(t\) такие, что

\[ sa+tb=\gcd(a,b). \]

НОД — это наименьшее натуральное число, представимое в виде целочисленной линейной комбинации \(a\) и \(b\).

Для чисел \(252\) и \(105\) обратный ход алгоритма даёт:

\[ 21=105-42\cdot 2, \]

а так как

\[ 42=252-105\cdot 2, \]

получаем

\[ 21=105-2(252-105\cdot 2)=105\cdot 5-2\cdot 252. \]

Итого:

\[ (-2)\cdot 252+5\cdot 105=21. \]

Тождество Безу важно для криптографии: если \(\gcd(a,b)=1\), то существует число \(s\), для которого

\[ sa\equiv 1\pmod b. \]

Это обратный элемент по модулю.

Теорема Ламе (\(1844\)) утверждает: количество шагов алгоритма Евклида для чисел \(a>b\) не превосходит примерно \(5\) умножить на число десятичных цифр числа \(b\).

Для чисел длиной \(300\) цифр, типичных в криптографических рассуждениях, это около \(1500\) шагов — мгновенно для современного процессора. Наихудший случай возникает, когда \(a\) и \(b\) — соседние числа Фибоначчи.

§ 11. Великие теоремы теории чисел

Пьер де Ферма (\(1607\)–\(1665\)) был юристом и математиком. Он почти не публиковал доказательств, а часто оставлял формулировки в письмах или на полях книг. Это породило целую традицию: понять, почему его утверждения верны.

Малая теорема Ферма формулируется так. Если \(p\) — простое число, а целое число \(a\) не делится на \(p\), то

\[ a^{p-1}\equiv 1\pmod p. \]

Эквивалентная форма:

\[ a^p\equiv a\pmod p \]

для любого целого \(a\).

Пример: пусть \(p=5\), \(a=3\). Тогда

\[ 3^4=81=16\cdot 5+1, \]

значит

\[ 3^4\equiv 1\pmod 5. \]

Малая теорема Ферма лежит в основе тестов простоты и через обобщения связана с RSA.

Теорема Эйлера

Леонард Эйлер (\(1707\)–\(1783\)) — один из самых продуктивных математиков в истории. С его именем связаны функция \(\varphi(n)\), формула Эйлера для многогранников, тождество \(e^{i\pi}+1=0\) и огромное количество результатов анализа, алгебры и теории чисел.

Для натуральных \(a\) и \(m\), взаимно простых между собой, теорема Эйлера утверждает:

\[ a^{\varphi(m)}\equiv 1\pmod m. \]

Здесь \(\varphi(m)\) — функция Эйлера: количество натуральных чисел от \(1\) до \(m\), взаимно простых с \(m\).

Если \(p\) простое, то \(\varphi(p)=p-1\), и теорема Эйлера превращается в малую теорему Ферма.

Пример: \(\varphi(10)=4\), потому что числа \(1\), \(3\), \(7\), \(9\) взаимно просты с \(10\). Проверим для \(a=3\):

\[ 3^4=81\equiv 1\pmod{10}. \]

Китайская теорема об остатках

Пусть \(m_1,m_2,\ldots,m_k\) — попарно взаимно простые числа. Тогда система сравнений

\[ x\equiv a_1\pmod {m_1}, \]

\[ x\equiv a_2\pmod {m_2}, \]

\[ \ldots \]

\[ x\equiv a_k\pmod {m_k} \]

имеет единственное решение по модулю

\[ M=m_1m_2\ldots m_k. \]

Пример:

\[ x\equiv 2\pmod 3, \]

\[ x\equiv 3\pmod 5, \]

\[ x\equiv 2\pmod 7. \]

Здесь \(M=105\). Перебором можно найти \(x=23\):

\[ 23\equiv 2\pmod 3, \]

\[ 23\equiv 3\pmod 5, \]

\[ 23\equiv 2\pmod 7. \]

Все решения имеют вид

\[ 23+105k. \]

Китайская теорема об остатках используется для ускорения вычислений RSA: вместо одной большой задачи можно решать несколько задач поменьше и затем собирать ответ обратно.

§ 12. Криптография: ваши данные защищены теорией чисел

Когда вы вводите пароль на сайте, шифруете переписку или покупаете что-то онлайн, за кулисами работает математика этой главы. Один из ключевых исторических алгоритмов — RSA, предложенный в \(1977\) году.

Он основан на асимметрии двух действий. Умножить два больших простых числа \(p\) и \(q\) легко:

\[ N=pq. \]

А вот разложить большое число \(N\) обратно на простые множители практически трудно для классических методов при современных размерах ключей.

Если известны \(p\) и \(q\), то функция Эйлера для \(N\) считается просто:

\[ \varphi(N)=(p-1)(q-1). \]

Если известен только \(N\), задача резко усложняется. На этой асимметрии и строится защита: открытый ключ можно публиковать, закрытый должен оставаться тайной.

В \(2002\) году Агравал, Каял и Саксена доказали результат, известный по названию их работы — PRIMES is in P: проверка простоты числа имеет детерминированный полиномиальный алгоритм. Тест AKS показывает, что простота — не мистическое свойство, а вычислимо проверяемая структура.

На практике, однако, часто используют более быстрые вероятностные тесты, например тест Миллера — Рабина. Они дают ответ очень быстро и с пренебрежимо малой вероятностью ошибки при правильном выборе параметров.

§ 13. Нерешённые задачи: наука без ответов

Теория чисел уникальна тем, что её главные открытые вопросы понятны школьнику, но недоступны лучшим математикам мира.

Гипотеза Гольдбаха, сформулированная в \(1742\) году, утверждает:

\[ \text{каждое чётное натуральное число больше }2\text{ является суммой двух простых чисел.} \]

Примеры:

\[ 4=2+2, \]

\[ 6=3+3, \]

\[ 8=3+5, \]

\[ 100=3+97=11+89=17+83. \]

Гипотеза проверена на огромных диапазонах, но общего доказательства нет.

Ближайший по духу результат — теорема Чэня (\(1973\)): каждое достаточно большое чётное число является суммой простого числа и числа, имеющего не более двух простых множителей.

Гипотеза о простых числах-близнецах

Простые числа-близнецы — это пары простых, отличающихся на \(2\):

\[ (3,5),\ (5,7),\ (11,13),\ (17,19),\ (29,31),\ldots \]

Гипотеза утверждает, что таких пар бесконечно много.

В \(2013\) году Итан Чжан доказал, что существует бесконечно много пар простых чисел, расстояние между которыми не превосходит \(70\,000\,000\). Позже Джеймс Мэйнард и другие математики существенно снизили эту границу — на момент подготовки этого текста известная граница составляет \(246\). Но разность \(2\) остаётся недоказанной.

Гипотеза Римана

Гипотеза Римана (\(1859\)) — одна из задач тысячелетия с премией \(1\,000\,000\) долларов. Она связывает дзета-функцию Римана с распределением простых чисел.

Мы знаем, что количество простых чисел, не превосходящих \(x\), приближённо равно

\[ \pi(x)\sim \frac{x}{\ln x}. \]

Гипотеза Римана описывает, насколько точно работает это приближение. Полная формулировка требует комплексного анализа, но её смысл связан с вопросом: насколько «регулярно» распределены простые числа среди натуральных?

Простые выглядят случайными, но за этой видимой случайностью стоит глубокая структура.

Гипотеза Коллатца

Возьмите любое натуральное число \(n\). Если \(n\) чётное, делите его на \(2\). Если нечётное, умножайте на \(3\) и прибавляйте \(1\). Гипотеза Коллатца утверждает: рано или поздно последовательность достигнет \(1\).

Для \(n=6\) получаем:

\[ 6\to 3\to 10\to 5\to 16\to 8\to 4\to 2\to 1. \]

Для \(n=27\) цепочка достигает \(9232\) на \(111\)-м шаге, а затем всё равно возвращается к \(1\).

Пол Эрдёш сказал о гипотезе Коллатца: «Математика ещё не готова к таким задачам». Это редкий случай, когда школьное правило порождает проблему, к которой современная математика пока не подобрала ключ.

Задачи к параграфу.

Базовая. Проверьте гипотезу Коллатца для \(n=11\). Сколько шагов нужно до числа \(1\)?

Аналитическая. Найдите \(n\) от \(1\) до \(100\), для которого цепочка Коллатца самая длинная.

Исследовательская. Попробуйте найти контрпример к гипотезе Гольдбаха для чётных чисел от \(4\) до \(1000\). Напишите программу. Контрпример вы не найдёте — гипотеза проверена далеко за пределами этого диапазона, — но сам процесс перебора многое говорит о том, почему доказательство в общем виде до сих пор не получено.

§ 14. Натуральные числа в коде и физике

Натуральные числа проявляются в физике всюду, где возникает дискретность. Квантовые числа атома, номера энергетических уровней, индексы состояний, число частиц в модели — всё это требует счёта.

Пифагоровы тройки

\[ a^2+b^2=c^2 \]

тоже связывают теорию чисел с геометрией и физикой. Их можно описать формулами

\[ a=m^2-n^2, \]

\[ b=2mn, \]

\[ c=m^2+n^2, \]

при подходящих натуральных \(m\) и \(n\).

Так арифметика становится языком структуры: она описывает не только «сколько», но и «как устроено».

Код ниже собирает три базовые процедуры: проверку простоты, разложение на множители и длину цепочки Коллатца.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors


def collatz_length(n):
    steps = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return steps

Что демонстрирует этот код? Теория чисел легко превращается в алгоритмы. Простота проверяется перебором делителей, разложение строится последовательным делением, гипотеза Коллатца становится циклом с условием.

§ 15. Итог: от счёта до бесконечности

Натуральные числа — первый математический объект, с которым встречается человек. И один из последних, тайны которого не исчерпаны.

В этой главе мы прошли путь от аксиом до нерешённых задач. Мы увидели, как признаки делимости вытекают из одной модульной идеи, как алгоритм Евклида в несколько строк кода вычисляет НОД, как простые числа становятся фундаментом криптографии, и почему простейшие формулировки могут оставаться недоказанными веками.

Главный вывод: натуральные числа — это не «школьная арифметика». Это фундамент математики, информатики и практической науки. От аксиом Пеано — к структуре компьютерной памяти. От алгоритма Евклида — к шифрованию. От признаков делимости — к открытым гипотезам.

Вернёмся к трём вопросам из начала главы.

1. Натуральных чисел бесконечно много. Их мощность — счётная бесконечность \(\aleph_0\).
2. Число \(1\) не является простым: простое число имеет ровно два натуральных делителя, а у \(1\) только один. Это соглашение сохраняет единственность разложения на простые множители.
3. Утверждение о том, что каждое чётное число больше \(2\) является суммой двух простых, называется гипотезой Гольдбаха. Она проверена на огромных диапазонах, но в общем виде не доказана.

Что осталось за рамками этой главы?

Теорема о распределении простых чисел:

\[ \pi(x)\sim \frac{x}{\ln x}, \]

доказанная Адамаром и де ла Валле Пуссеном в \(1896\) году. Теорема Дирихле о простых числах в арифметических прогрессиях. Квадратичные вычеты и закон взаимности Гаусса. Алгебраическая теория чисел. \(p\)-адические числа — альтернативная числовая вселенная, где расстояние устроено иначе, чем на привычной прямой.

Это не случайные «темы на потом». Это продолжения той же линии: натуральные числа просты на входе, но бесконечно глубоки внутри.

§ 16. Мост к следующей главе: число в машине

Натуральные числа чисты, бесконечны и совершенны в своей абстракции. Но когда число попадает в процессор, оно перестаёт быть идеальным объектом: его нужно закодировать в конечное число битов, вписать в диапазон, обработать по правилам конкретного типа данных.

Тип uint32 хранит числа от \(0\) до

\[ 2^{32}-1, \]

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

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

Этим мы займёмся в главе «Арифметика компьютера: точность, ошибки и цена вычислений».