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

Большинство людей считает, что математика либо полезна, либо абстрактна. Теория чисел занимает странное промежуточное положение. Любители её обожают. Профессионалы одержимы ею. Задачи легко понять. Очень легко. Десятилетний ребёнок может осознать суть вопроса. Но решение? Для этого обычно требуется инструментарий уровня доктора наук.

На протяжении веков эта ветвь математики считалась самой чистой и самой бесполезной формой математики. Никаких мостов не строили. Никаких двигателей не проектировали. Только числа.

Затем появились компьютеры.

Внезапно теория чисел стала основой цифровой безопасности. Шифрование опирается на неё. Цифровая связь зависит от неё. Современные технологии превратили абстрактное любопытство в практическую необходимость. Компьютеры также помогли нам разлагать на множители огромные числа, находить простые числа и проверять идеи, которые ранее было невозможно проверить.

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

Как древние цивилизации открыли теорию чисел

Счёт — древнее занятие. Очень древнее.

Археологи нашли в регионе Конго в Африку кость возрастом 10 000 лет. На ней вырезаны зарубки. Кто-то считал что-то. Возможно, скот. Возможно, дни. Это первый шаг к пониманию множественности.

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

Вавилоняне были особенно проницательны. Табличка под названием Плимптон 322, датированная примерно 1700 годом до н. э., показывает, что они понимали пифагоровы тройки задолго до рождения Пифагора. В современной записи это наборы чисел, где $x^2 + y^2 = z^2$. Один пример на табличке использует числа 2291, 2700 и 3541. Математика сходится идеально.

Это было не просто случайное вычисление. Это была теоретико-числовая изощрённость. Но у них не было общей теории. Никакой структуры. Только изолированные результаты.

Для этого нам нужно обратиться к Древней Греции. Они смешали мистические настроения пифагорейцев с холодной, жёсткой логикой Евклида.

Пифагор и мистицизм чисел

Пифагор жил в южной Италии примерно в 580–500 годах до н. э. У него было последователей. Очень много.

Его философия была простой, но радикальной: число — это объединяющая концепция вселенной. Движение планет? Числа. Музыкальная гармония? Числа.

Из-за этой веры пифагорейцы приписывали определённым целым числам квазирациональные свойства. Они любили совершенные числа. Совершенное число равно сумме своих собственных делителей.

Возьмём 6. Его собственные делители — 1, 2 и 3. Сложим их: $1 + 2 + 3 = 6$. Готово.

Другой пример — 28. Его делители — 1, 2, 4, 7 и 14. Суммируем: $1 + 2 + 4 + 7 + 14 = 28$.

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

Грекам также нравились дружественные числа. Это пары целых чисел, где каждое равно сумме собственных делителей другого. Они знали только одну пару: 220 и 284.

Проверим математику. Делители числа 284 — это 1, 2, 4, 71 и 142. Они в сумме дают 220. Делители числа 220 — это 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110. Они в сумме дают 284.

Для человека, склонного к числовому мистицизму, это выглядит как магия.

Евклид принёс логику

Евклида не интересовал мистицизм. Он хотел строгости.

В книге VII «Начал» (ок. 300 г. до н. э.) он определил число как «множество, составленное из единиц». Обратите внимание на множественное число. Для Евклида 1 не было числом. 2 было наименьшим числом.

Он определил простое число как число, «измеряемое только единицей». Иными словами, его единственный собственный делитель — 1. Составные числа — это всё остальное. Совершенные числа остаются теми, которые равны сумме своих частей.

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

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

Во-вторых, он установил теорему о единственности разложения. Также известную как основная теорема арифметики. Она гласит, что любое целое число можно разложить на простые множители единственным способом.

Возьмём 1960. Его разложение на простые множители: $2 \times 2 \times 2 \times 5 \times 7 \times 7$. Никакая другая комбинация простых чисел не даёт в произведении 1960. Доказательство Евклида не было безупречным по современным стандартам, но суть была на месте.

В-третьих, Евклид доказал, что не существует конечного набора всех простых чисел. Он показал, что всегда можно найти ещё одно.

Его аргумент, Предложение 20 книги IX, элегантен. Возьмите любой конечный список простых чисел: $a, b, c, \dots, n$. Умножьте их все вместе. Затем прибавьте 1. Назовём это число $N$.

$N = (a \times b \times c \times \dots \times n) + 1$

Теперь рассмотрим альтернативы.

Последний удар Евклида и бесконечный список

Вот логика, которая разрушает идею о существовании последнего простого числа.

Возьмите любой список простых чисел. Умножьте их все друг на друга. Прибавьте единицу. Назовите результат N.

Если N — простое число, то это новое число. Оно больше любого числа из вашего исходного списка. Его не может быть в списке. Просто.

Если N не является простым, оно составное. У него обязательно есть простые множители. Евклид показал, что эти множители также не могут входить в ваш исходный список.

Почему? Потому что при делении N на любое из исходных простых чисел в остатке всегда получается 1. Ни одно из них не делится на N нацело.

Попробуйте. Начните с 2, 7 и 11. Умножьте их. Прибавьте 1. Получите 155.
155 — составное число. Его множители — 5 и 31.
Ни 5, ни 31 не было в вашей исходной группе. Вы нашли новые простые числа.

Это доказывает, что простые числа никогда не заканчиваются. Список бесконечен.

Евклид не остановился на этом. Он завершил Книгу IX мощным открытием.

Он нашел рецепт для совершенных чисел.

Совершенное число равно сумме своих собственных делителей. 28 — одно из них. 1+2+4+7+14 = 28.

Правило Евклида: Возьмите степени двойки. Сложите их. 1 + 2 + 4 + … + 2^k.
Если эта сумма является простым числом, умножьте ее на 2^k. Результат будет совершенным.

Пример: 1 + 2 + 4 = 7. Семь — простое число.
Умножьте 7 на 4 (что равно 2^2). Получите 28.
Работает. Это был огромный скачок для своего времени.

Диофант и одержимость целыми числами

Перенесемся в Александрию. Примерно 250 год н.э.

Диофант написал «Арифметику». Его интересовала одна вещь: целые числа.

Никаких дробей. Никаких десятичных дробей. Только целые числа.

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

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

В символах: найдите целые числа x, y, z так, чтобы (x^2)^2 + (y^3)^2 = z^2.

Вы можете легко найти действительные числа, которые подходят. x = корень из 2, y = 1, z = корень из 5.
Но целые числа? Это сложно.

Одно решение: x = 6, y = 3, z = 45.
Проверьте. 36 в квадрате равно 1296. 3 в кубе равно 27. 27 в квадрате равно 729.
1296 + 729 = 2025.
Квадратный корень из 2025 равен 45.

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

Восток вступает в игру, пока Европа спит

Европа погрузилась во тьму после падения Рима. Теория чисел встала на месте.

Азия не остановилась.

Китайским астрономам нужны были более точные календари. Они столкнулись с трудностями в модульной арифметике.

Сунь-Цзы примерно в 250 году н.э. сформулировал классическую задачу.
Найдите число, которое:
— Дает остаток 2 при делении на 3
— Дает остаток 3 при делении на 5
— Дает остаток 2 при делении на 7

Ответ — 23.

Проверьте. 23 / 3 дает 7 в остатке 2. 23 / 5 дает 4 в остатке 3. 23 / 7 дает 3 в остатке 2.

Тысячу лет спустя Цинь Цзюшао формализовал это. Мы называем это китайской теоремой об остатках. Она до сих пор используется в информатике.

Тем временем в Индии Брахмагупта был занят в VII веке.

Он взялся за то, что мы теперь ошибочно называем уравнением Пелля.

Найдите целые числа x и y такие, что 92x^2 + 1 = y^2.

Он ставил на кон: кто решит это за год, может называть себя математиком.

Решение: x = 120 и y = 1151.

92 умножить на 14 400 плюс 1 равно 1 324 801.
1151 в квадрате равно 1 324 801.

Он также подарил нам индо-арабские цифры.

Мы используем их каждый день. Десятичная система. Включая ноль.
Мир принял их, потому что они просты. Индийцы использовали их к 800 году н.э.

Затем мусульманский мир взял инициативу на себя.

Багдад в IX веке был центром притяжения. Ученые переводили греческие тексты. Затем они их улучшали.

Табит ибн Кура нашел новые дружественные числа.
Это пары, в которых сумма делителей одного числа равна другому.

Он нашел 17 296 и 18 416.
Греки знали одну пару. Табит нашел другую.

Ферма меняет правила игры

Теория чисел проникла в Европу во время Ренессанса.

Ее игнорировали.

Математики любили геометрию. Они любили алгебру. Вероятность была в тренде.
Теорию чисел считали игрушкой. Парламентской забавой.

Затем появился Пьер де Ферма.

1601–1665. Французский магистрат. Любитель.
Он почти ничего не публиковал. Он писал письма.

Он изменил все.

Ферма замечал закономерности, которые другие пропускали. Он ставил задачи, на решение которых уходили столетия.

Вот как он преобразил эту область.

Малая теорема Ферма

Если p — простое число, а a — любое целое число, то p делит a^p — a.

Пусть p = 7. Пусть a = 12.
12^7 — огромное число. Вычтите 12.
Разделите на 7.
Делится нацело. Без остатка.

Это неочевидно. Сегодня это мощный инструмент для криптографии.

Суммы квадратов

Ферма рассматривал нечетные простые числа. Он разделил их на два лагеря.

Тип 1: 4k + 1. Например, 5, 13, 17, 97.
Тип 2: 4k — 1. Например, 3, 7, 11, 79.

Ферма утверждал, что простые числа Типа 1 всегда можно представить в виде суммы двух квадратов.
5 = 2^2 + 1^2.
97 = 9^2 + 4^2.

Простые числа Типа 2 нельзя.
3 не является суммой двух квадратов. 79 тоже нет.

Это разделение стало вехой в теории чисел.

Теорема о четырех квадратах

В 1638 году Ферма бросил еще одну бомбу.

Любое целое число является суммой четырех или меньшего количества квадратов.

Он сказал, что у него есть доказательство. Но он никогда не поделился им.

Это стиль Ферма. Заявить правду. Оставить работу другим.

Это отношение превратило теорию чисел из любопытства в серьезную дисциплину. Оно заставило математиков копать глубже. Доказывать вещи.

Эра игривых догадок закончилась.

Как «невозможный» треуголь Ферма и ошибочные простые числа задали сцену

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

Подумайте об этом. Вам нужны целые числа $x$, $y$ и $z$ такие, что $x^2 + y^2 = z^2$. Но вам также нужно, чтобы площадь, которая равна $\frac{xy}{2}$, равнялась некоторому целому числу $w^2$. Ферма заявил, что такая комбинация не существует.

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

Вы получаете бесконечную цепочку все меньших и меньших положительных целых чисел. Но это невозможно. Положительные целые числа имеют нижнюю границу. Они останавливаются на 1. Поскольку вы не можете спускаться вечно, исходное предположение должно быть неверным. Такого треугольника не существует.

Затем было его предположение о простых числах. Ферма утверждал, что числа вида $2^{2^n} + 1$ всегда являются простыми. Он проверил первые несколько случаев:
— $n=0$: 3 (простое)
— $n=1$: 5 (простое)
— $n=2$: 17 (простое)
— $n=3$: 257 (простое)
— $n=4$: 65 537 (простое)

Теперь они называются простыми числами Ферма. Это выглядело как надежный паттерн. До тех пор, пока не перестало. Следующее число в последовательности, $2^{2^5} + 1$, равно 4 294 967 297. Оно не является простым. Ферма ошибся. Даже гении могут упускать из виду детали.

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

В математических терминах: $x^n + y^n = z^n$ не имеет целочисленных решений для $n > 2$.

Он добавил дерзкую заметку: он нашел «истинно чудесное доказательство», но поле было слишком узким, чтобы записать его. Это стало Последней теоремой Ферма. В течение 350 лет она оставалась неразрешенной. Она стала самой известной открытой проблемой в математике.

Почему теория чисел игнорировалась в течение века

Ферма был гениальным, но теория чисел не взлетела сразу. Почему? Отчасти потому, что он редко публиковал полные доказательства. Но большая проблема заключалась в появлении исчисления в конце 1600-х годов.

Исчисление решало реальные проблемы. Оно помогало физикам, астрономам и инженерам понимать движение, силы и орбиты. Теория чисел, напротив, казалась «чистой». У нее не было очевидного применения для строительства мостов или предсказания планетарных путей. Ученые гнались за исчислением. Теория чисел лежала на полке.

Как Эйлер спас теорию чисел

Вступает Леонард Эйлер. Родившись в 1707 году, Эйлер был швейцарцем, невероятно плодовитым и, возможно, самым влиятельным математиком 18-го века. Когда он решил заняться теорией чисел, предмет внезапно стал важным.

Изначально Эйлеру тоже было не до этого. Он был занят другой математикой. Но Кристиан Гольдбах, дипломат и энтузиаст теории чисел, не позволил ему игнорировать ее. Гольдбах писал Эйлеру как настойчивый продавец.

1 декабря 1729 года Гольдбах спросил: «Знаете ли вы наблюдение Ферма о том, что все числа $2^{2^n} + 1$ являются простыми?»

Эйлер клюнул на приманку. Он проверил утверждение Ферма. И он его разрушил. Он показал, что 4 294 967 297 делится на 641. Ферма снова ошибся.

Это было началом. В течение следующих 50 лет Эйлер опубликовал более 1000 страниц по теории чисел. Он доказал многие другие утверждения Ферма:
— Он доказал Малую теорему Ферма.
— Он доказал, что простые числа вида $4k + 1$ могут быть записаны как сумма двух квадратов.
— Он работал над совершенными числами, показывая, что четные совершенные числа должны следовать форме, найденной Евклидом 2000 лет назад.
— Он нашел 58 новых пар дружественных чисел. До Эйлера были известны только три пары.

Эйлер не мог решить все. Ему удалось доказать Последнюю теорему Ферма для случаев, когда $n=3$ и $n=4$. Но общий случай его остановил. Он также не смог доказать гипотезу Гольдбаха — идею о том, что каждое четное число больше 2 является суммой двух простых чисел. Он верил, что это правда, но не мог доказать это.

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

19-й век и сумма четырех квадратов

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

Вскоре после этого Лагранж установил теорему Вильсона. Она гласит, что число $p$ является простым тогда и только тогда, когда $p$ делит без остатка $[(p-1)!] + 1$.

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

Гаусс устанавливает правила современной теории чисел

Карл Фридрих Гаусс устроил взрыв в 1801 году. «Арифметические исследования» (Disquisitiones Arithmeticae ) были не просто еще одной математической книгой. Это была библия для теоретиков чисел. Он взял хаотичные работы всех предшественников, систематизировал их и затем уверенно обогнал их всех.

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

Чтобы сделать математику более стройной, он ввел понятие сравнения. Если вы пишете a ≡ b (mod m ), это означает, что m делит без остатка разность a − b. Возьмем 39 и 4. Их разность равна 35. 7 делит 35. Следовательно, 39 ≡ 4 (mod 7).

Эта простая идея изменила всё. В сочетании с малой теоремой Ферма она стала основным инструментом. Без неё современная теория чисел выглядела бы совершенно иначе.

Почему Дирихле изменил правила игры с помощью исчисления

Гаусс вдохновил целое поколение. Софи Жермен была одержима теорией чисел. Она добилась реального прогресса в решении последней теоремы Ферма. Адриен-Мари Лежандр и Петер Густав Лежён Дирихле доказали её для n = 5. Сумма двух чисел в пятой степени не может быть числом в пятой степени.

Эрнст Куммер продвинулся дальше в 1847 году. Он показал, что теорема верна для большого класса показателей. Но он не смог исключить возможность её неверности в других случаях. Проблема оставалась открытой.

Дирихле держал копию «Арифметических исследований» Гаусса у своей кровати. Он читал её по ночам. И он изменил всю область. Он доказал, что если a и b не имеют общих множителей, то арифметическая прогрессия a, a + b, a + 2b, a + 3b, … содержит бесконечно много простых чисел.

Это означает, что существует бесконечно много простых чисел вида 4k + 1. И бесконечно много простых чисел вида 4k − 1.

Результат был значительным. Но метод был ещё важнее. Дирихле использовал исчисление для доказательства результата теории чисел. Большинство математиков считали это невозможным. Или, по крайней мере, странным. Это сочетание анализа и арифметики породило аналитическую теорию чисел.

Как теорема о простых числах подсчитывает простые числа

Теорема о простых числах стоит в ряду величайших достижений XIX века. Её нужно кратко объяснить.

Пусть π(n ) — количество простых чисел, меньших или равных n.
Для n = 10 простые числа: 2, 3, 5, 7. Значит, π(10) = 4.
Для n = 25, π(25) = 9.
Для n = 100, π(100) = 25.

Теперь посмотрим на отношение. π(n )/n показывает, какая доля чисел до n является простой.
π(10)/10 = 0,40. Сорок процентов.
По мере роста n этот процент падает. Простые числа становятся реже.

Как теорема о простых числах отображает хаос простых чисел

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

Для большого числа n доля простых чисел до n — записываемая как π(n )/n — приблизительно равна 1/log n. Этот логарифм — натуральный логарифм. Связь простых чисел с логарифмами кажется странной. Это необыкновенно. Она связывает дискретное счетное с непрерывными кривыми.

Молодой Гаусс первым заметил это. Он перелистывал таблицы логарифмов, всматривался в простые числа, и у него в голове щелкнуло. Позже Бернхард Риман и Пафнутий Чебышев продвинули математику дальше. Но потребовалось время до 1896 года, чтобы Жак Адамар и Шарль Жан де ла Валле-Пуссен фактически доказали это. Красивое завершение XIX века.

Взрыв исследований в теории чисел в XX веке

Затем наступил XX век. Теория чисел не просто росла; она взорвалась. Классические методы встретили аналитические техники, и выросли новые подразделы. Алгебраическая теория чисел. Геометрическая теория чисел. Комбинаторная теория чисел. Концепции стали абстрактными. Инструменты стали сложными. Ферма не мог этого представить.

Шриниваса Рамануджан появился на сцене в начале века. У него почти не было формального образования, и он умер молодым, но он производил гениальные идеи, как вода из крана. Он любил аналитическую теорию чисел. Его статьи имели такие названия, как «Высоко составные числа», и доказывали, что почти все числа n состоят примерно из log(log n ) простых множителей. Плотная материя. Но точная.

Затем был Поль Эрдёш. Венгерский гений, который жил из чемодана. Он постоянно путешествовал, перемещаясь между университетами, преследуя математику. В 18 лет он упростил теорему Чебышева: если n ≥ 2, то всегда есть простое число между n и 2n. Он опубликовал более 1500 статей с более чем 500 соавторами. Он появлялся без предупреждения, говорил: «Мой мозг открыт», и погружался в работу. Без сна. Без дома. Только математика.

Компьютеры и криптография меняют игру

Две вещи позже изменили всё. Компьютеры. И шифрование.

Компьютеры применили грубую силу к старым вопросам. Эйлер думал, что нужно как минимум четыре четвертых степени, чтобы их сумма равнялась четвертой степени. Он ошибался. В 1988 году Ноам Элькис использовал компьютер, чтобы найти контрпример:

2,682,440^4 + 15,365,639^4 + 18,796,760^4 = 20,615,673^4

Результат имеет 30 цифр. Эйлер пропустил это, потому что числа огромны. Компьютер не пропустил.

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

Кульминация: решение последней теоремы Ферма

В 1995 году Эндрю Уайлс доказал последнюю теорему Ферма. Ричард Тейлор помог. Доказательство состояло из 130 страниц. Сложное. Плотное. Оно не поместилось бы ни в одном поле, как утверждал Ферма. Но оно было верным. Век усилий, наконец, разрешен.

Неразрешенные тайны теории чисел

Но область не закончена. Многие проблемы остаются открытыми. Они звучат просто. Они не такие.

  • Существуют ли нечетные совершенные числа?
  • Существует ли бесконечно много простых чисел вида n ^2 + 1?
  • Существует ли бесконечно много простых близнецов (пар, таких как 5 и 7)?
  • Верна ли гипотеза Гольдбаха? (Каждое четное число является суммой двух простых чисел.)

Эйлер пытался. Все после него пытались. Без удачи.

Институт математики Клэя в Кембридже, Массачусетс, назвал семь проблем тысячелетия в 2000 году. Каждая сопровождается миллионом долларов. Может быть, эти проблемы будут решены. Может быть, нет. Эрик Темпл Белл назвал теорию чисел «последним великим нецивилизованным континентом математики». Он не ошибся.

Теория чисел стара. Она свежа. Проблемы цепляют, потому что они выглядят простыми. Они обманчиво сложны. Красивы тоже. Гаусс назвал ее королевой математики. Он не льстил. Он описывал иерархию.