Математика целых чисел и теория чисел

Введение

Теория чисел (или арифметика, или высшая арифметика в более раннем употреблении) — это раздел чистой математики, посвященный прежде всего изучению целых чисел и арифметических функций. Немецкий математик Карл Фридрих Гаусс (1777–1855) говорил: «Математика — царица наук, а теория чисел — царица математики». Теоретики чисел изучают простые числа, а также свойства математических объектов, построенных из целых чисел (например, рациональных чисел) или определенных как обобщения целых чисел (например, алгебраических целых). Целые числа можно рассматривать как сами по себе или как решения уравнений (диофантова геометрия). Вопросы теории чисел часто лучше всего понимаются посредством изучения аналитических объектов (например, дзета-функции Римана), которые кодируют свойства целых чисел, простых чисел или других объектов теории чисел тем или иным образом (аналитическая теория чисел). Можно также изучать действительные числа в связи с рациональными числами, например, как приближаемые последними (диофантово приближение). Более старый термин для теории чисел — арифметика. К началу двадцатого века он был вытеснен термином «теория чисел». (Слово «арифметика» в обиходе означает «элементарные вычисления»; оно также приобрело другие значения в математической логике, как в арифметике Пеано, и в информатике, как в арифметике с плавающей точкой.) Использование термина «арифметика» для обозначения теории чисел вновь приобрело некоторую популярность во второй половине XX века, возможно, отчасти благодаря французскому влиянию. В частности, прилагательное «арифметический» обычно предпочтительнее, чем «теоретико-числовой».

Арябхата, Брахмагупта, Бхаскара

Хотя греческая астрономия, вероятно, повлияла на индийское обучение, вплоть до внедрения тригонометрии, похоже, что индийская математика в остальном является исконной традицией; в частности, нет никаких свидетельств того, что «Начала» Евклида достигли Индии до XVIII века. Āрьябхата (476–550 гг. н.э.) показал, что пары одновременно сравнимых уравнений можно решить методом, который он назвал куттака, или «пульверизатор»; это процедура, близкая к (обобщению) алгоритма Евклида, который, вероятно, был открыт независимо в Индии. Āрьябхата, по-видимому, имел в виду применение к астрономическим вычислениям. Брахмагупта (628 г. н.э.) начал систематическое изучение неопределённых квадратных уравнений — в частности, ошибочно названного уравнения Пелля, которым, возможно, впервые заинтересовался Архимед, и которое не начали решать на Западе до времени Ферма и Эйлера. Позднее санскритские авторы продолжили его работу, используя техническую терминологию Брахмагупты. Общая процедура (чакравала, или «циклический метод») для решения уравнения Пелля была, наконец, найдена Джаядевой (упоминается в XI веке; его работа в противном случае утеряна); самое раннее сохранившееся изложение встречается в «Бӣджа гаṇита» Бхаскары II (XII век). Индийская математика оставалась в значительной степени неизвестной в Европе до конца XVIII века; работы Брахмагупты и Бхаскары были переведены на английский язык в 1817 году Генри Кольбруком.

Арифметика в исламский золотой век

В начале IX века халиф Аль-Мамун приказал перевести множество греческих математических трудов и как минимум один санскритский труд (Синдхинд, который, возможно, является, а возможно, и не является «Брахмасфутасиддханта» Брахмагупты). Основной труд Диофанта, «Арифметика», был переведен на арабский язык Кустой ибн Лукой (820–912). Часть трактата «Аль-Фахри» (аль-Караджи, 953 – ок. 1029) в определенной степени основывается на нем. По словам Рашеда Рошди, современник аль-Караджи Ибн аль-Хайсам знал то, что впоследствии стало известно как теорема Уилсона.

Западная Европа в средние века

Кроме трактата Фибоначчи о квадратах в арифметической прогрессии – он путешествовал и изучал Северную Африку и Константинополь – в Средние века в Западной Европе практически не было работ по теории чисел. Ситуация начала меняться в Европе в конце эпохи Возрождения благодаря вновь обретенному интересу к трудам античной Греции. Толчком послужила критическая работа с текстом и перевод на латынь «Арифметики» Диофанта.

Эйлер

Интерес Леонарда Эйлера (1707–1783) к теории чисел впервые проявился в 1729 году, когда его друг, любитель Гольдбах, обратил его внимание на некоторые работы Ферма по этой теме. Это событие называют «возрождением» современной теории чисел, после относительной неудачи Ферма в привлечении внимания современников к этой области. Работы Эйлера по теории чисел включают в себя следующее:

Доказательства утверждений Ферма. Это включает в себя малую теорему Ферма (обобщённую Эйлером на не простые модули); факт, что если и только если ; начальные работы, направленные на доказательство того, что каждое целое число является суммой четырёх квадратов (первое полное доказательство принадлежит Жозефу Луи Лагранжу (1770), вскоре усовершенствованное самим Эйлером); отсутствие ненулевых целочисленных решений уравнения (что подразумевает случай n=4 последней теоремы Ферма, а также случай n=3, который Эйлер доказал схожим методом). Уравнение Пелля, впервые ошибочно названное Эйлером. Он писал о связи между цепными дробями и уравнением Пелля. Первые шаги к аналитической теории чисел. В своих работах о суммах четырёх квадратов, разбиениях, пентагональных числах и распределении простых чисел Эйлер стал пионером в использовании методов, которые можно рассматривать как анализ (в частности, бесконечных рядов) в теории чисел. Поскольку он жил до развития комплексного анализа, большая часть его работ ограничивается формальными манипуляциями степенными рядами. Тем не менее, он проделал некоторые заметные (хотя и не полностью строгие) ранние исследования того, что впоследствии было названо дзета-функцией Римана. Квадратичные формы. Следуя примеру Ферма, Эйлер продолжил исследования вопроса о том, какие простые числа можно представить в виде , некоторые из которых предвосхищают закон квадратичной взаимности. Диофантовы уравнения. Эйлер работал над некоторыми диофантовыми уравнениями рода 0 и 1. В частности, он изучал работы Диофанта, пытаясь их систематизировать, но для этого ещё не было подходящего времени — алгебраическая геометрия находилась в зачаточном состоянии. Он заметил связь между диофантовыми задачами и эллиптическими интегралами, изучение которых он сам инициировал.

Лагранж, Лежендр и Гаус

Джозеф Луи Лагранж (1736–1813) был первым, кто дал полные доказательства некоторых работ и наблюдений Ферма и Эйлера, например, теоремы о четырех квадратах и основной теории ошибочно названного «уравнения Пелля» (для которого алгоритмическое решение было найдено Ферма и его современниками, а также Джаядевой и Бхаскарой II ранее). Он также изучал квадратичные формы в полной общности (в отличие от) – определяя их отношение эквивалентности, показывая, как привести их к несократимому виду и т. д. Адриен Мари Лежандр (1752–1833) первым сформулировал закон квадратичной взаимности. Он также выдвинул предположение, эквивалентное теореме о простых числах и теореме Дирихле об арифметических прогрессиях. Он дал полное рассмотрение уравнения и работал над квадратичными формами в направлении, впоследствии полностью разработанном Гауссом. В старости он первым доказал последнюю теорему Ферма для n=5 (завершив работу Питера Густава Лежена Дирихле и отдав должное как ему, так и Софи Жермен). В своей работе «Disquisitiones Arithmeticae» (1798) Карл Фридрих Гаусс (1777–1855) доказал закон квадратичной взаимности и разработал теорию квадратичных форм (в частности, определив их композицию). Он также ввел некоторые основные обозначения (конгруэнции) и посвятил раздел вычислительным вопросам, включая тесты на простоту. В последнем разделе «Disquisitiones» установлена связь между корнями из единицы и теорией чисел: теория деления круга, рассматриваемая в § 7, сама по себе не относится к арифметике, но ее принципы могут быть выведены только из высшей арифметики. Таким образом, Гаусс, возможно, сделал первый шаг к работам Эвариста Галуа и алгебраической теории чисел.

Элементарная теория чисел

Термин "элементарный" обычно обозначает метод, который не использует комплексный анализ. Например, теорема о простых числах была впервые доказана с использованием комплексного анализа в 1896 году, но элементарное доказательство было найдено лишь в 1949 году Эрдошем и Селбергом. Этот термин несколько неоднозначен: например, доказательства, основанные на комплексных теоремах Таубера (таких как теорема Винера — Икехары), часто считаются весьма проницательными, но не элементарными, несмотря на использование анализа Фурье, а не комплексного анализа как такового. Как и в других случаях, элементарное доказательство может быть длиннее и сложнее для большинства читателей, чем доказательство, использующее более сложные методы. Теория чисел имеет репутацию области, результаты которой зачастую можно объяснить широкой публике. Однако доказательства этих результатов не отличаются особой доступностью, отчасти из-за необычно широкого спектра используемых в них инструментов по сравнению с другими областями математики.

Другие подполя

Написанные ниже области возникли не ранее середины двадцатого века, даже если они опираются на более ранние наработки. Например, как будет объяснено ниже, сама идея алгоритмов в теории чисел очень стара, в некотором смысле даже старше понятия доказательства; однако современное изучение вычислимости началось лишь в 1930-х и 1940-х годах, а теория вычислительной сложности – в 1970-х.

Вероятностная теория чисел

Большая часть вероятностной теории чисел может рассматриваться как важный частный случай изучения переменных, которые почти, но не совсем, независимы. Например, событие, что случайное целое число между единицей и миллионом делится на два, и событие, что оно делится на три, почти независимы, но не совсем. Иногда утверждают, что вероятностная комбинаторика использует тот факт, что любое событие с вероятностью больше нуля должно произойти хотя бы раз; с той же справедливостью можно сказать, что многие применения вероятностной теории чисел основаны на том, что любое необычное явление должно быть редким. Если удается показать, что определенные алгебраические объекты (например, рациональные или целые решения определенных уравнений) находятся в хвосте некоторого осмысленно заданного распределения, то следует, что таких объектов должно быть немного; это вполне конкретное не-вероятностное утверждение, вытекающее из вероятностного. Подчас нестрогий, вероятностный подход приводит к ряду эвристических алгоритмов и нерешенных проблем, в частности, к гипотезе Крамера.

Вычислительная теория чисел

В то время как само слово "алгоритм" восходит лишь к определенным читателям аль-Хорезми, детальные описания методов решения появились раньше доказательств: эти методы (то есть алгоритмы) столь же древни, как и любая узнаваемая математика — древнеегипетская, вавилонская, ведийская, китайская, — тогда как доказательства возникли только у греков классического периода. Ранним примером служит то, что мы сейчас называем алгоритмом Евклида. В своей базовой форме (а именно, как алгоритм вычисления наибольшего общего делителя) он представлен как Предложение 2 Книги VII в "Началах", вместе с доказательством его корректности. Однако в форме, часто используемой в теории чисел (а именно, как алгоритм для нахождения целочисленных решений уравнения, или, что эквивалентно, для определения чисел, существование которых гарантируется китайской теоремой об остатках), он впервые встречается в трудах Арьябхаты (V–VI века н.э.) как алгоритм, называемый куттака ("измельчитель"), без доказательства корректности. Существует два основных вопроса: "Возможно ли это вычислить?" и "Возможно ли вычислить это быстро?". Любой может проверить, является ли число простым, или, если нет, разложить его на простые множители; быстрое разложение — это уже другая задача. Сейчас нам известны быстрые алгоритмы для проверки простоты, но, несмотря на значительные теоретические и практические усилия, действительно быстрого алгоритма для факторизации не существует. Сложность вычислений может быть полезной: современные протоколы шифрования сообщений (например, RSA) основаны на функциях, известных всем, но обратные к которым известны лишь немногим избранным и потребовали бы слишком много времени для самостоятельного вычисления. Например, эти функции могут быть такими, что их обратные можно вычислить только при факторизации определенных больших целых чисел. Хотя известно множество сложных вычислительных задач за пределами теории чисел, большинство работающих протоколов шифрования в настоящее время основаны на сложности нескольких задач из теории чисел. Некоторые вещи могут быть в принципе невычислимы; более того, это можно доказать в некоторых случаях. Например, в 1970 году было доказано, как решение десятой проблемы Гильберта, что не существует машины Тьюринга, способной решить все диофантовы уравнения. В частности, это означает, что для любого вычислимо перечислимого набора аксиом существуют диофантовы уравнения, для которых нет доказательства, исходя из этих аксиом, наличия или отсутствия целочисленных решений. (Мы неизбежно говорим о диофантовых уравнениях, не имеющих целочисленных решений, поскольку, если дано диофантово уравнение с хотя бы одним решением, само это решение служит доказательством существования решения. Мы не можем доказать, что конкретное диофантово уравнение относится к этому типу, так как это означало бы, что оно не имеет решений.)

Призы

Американское математическое общество присуждает премию Коула по теории чисел. Кроме того, теория чисел – одна из трех математических областей, удостоенных премии Ферма.