Теория чисел (или арифметика или высшая арифметика в более старом использовании) — раздел чистой математики, посвященный в первую очередь изучению целых чисел и арифметических функций . Немецкий математик Карл Фридрих Гаусс (1777–1855) сказал: «Математика — царица наук, а теория чисел — царица математики». [1] Специалисты по теории чисел изучают простые числа , а также свойства математических объектов, построенных из целых чисел (например, рациональных чисел ) или определенных как обобщения целых чисел (например, алгебраических целых чисел ).
Целые числа можно рассматривать как сами по себе, так и как решения уравнений ( диофантова геометрия ). Вопросы теории чисел часто лучше всего понимаются через изучение аналитических объектов (например, дзета-функции Римана ), которые кодируют свойства целых чисел, простых чисел или других числовых теоретико-числовых объектов каким-либо образом ( аналитическая теория чисел ). Можно также изучать действительные числа в связи с рациональными числами; например, как приближенные последними ( диофантовы приближения ).
Более старый термин для теории чисел — арифметика . К началу двадцатого века он был вытеснен теорией чисел . [примечание 1] (Слово арифметика используется широкой публикой для обозначения « элементарных вычислений »; оно также приобрело другие значения в математической логике , как в арифметике Пеано , и в компьютерной науке , как в арифметике с плавающей точкой .) Использование термина арифметика для теории чисел вернулось к некоторой почве во второй половине двадцатого века, возможно, отчасти из-за французского влияния. [примечание 2] В частности, арифметический обычно предпочитают как прилагательное к теоретико-числовому .
Самая ранняя историческая находка арифметического характера — фрагмент таблицы: сломанная глиняная табличка Plimpton 322 ( Ларса, Месопотамия , ок. 1800 г. до н. э.) содержит список « пифагорейских троек », то есть целых чисел, таких что . Троек слишком много и они слишком велики, чтобы быть полученными методом грубой силы . Заголовок над первым столбцом гласит: «Такилтум диагонали , который был вычтен таким образом, что ширина...» [2]
Структура таблицы предполагает [3] , что она была создана с помощью того, что на современном языке можно назвать тождеством
что подразумевается в обычных древневавилонских упражнениях. [4] Если использовался какой-то другой метод, [5] тройки сначала строились, а затем переупорядочивались , предположительно для фактического использования в качестве «таблицы», например, с целью приложений.
Неизвестно, какими могли быть эти приложения, или могли ли они быть; вавилонская астрономия , например, действительно вошла в свою собственную жизнь только позже. Вместо этого было высказано предположение, что таблица была источником числовых примеров для школьных задач. [6] [примечание 3]
Хотя свидетельства вавилонской теории чисел сохранились только в табличке Плимптона 322, некоторые авторы утверждают, что вавилонская алгебра была исключительно хорошо развита и включала основы современной элементарной алгебры . [7] Поздние неоплатонические источники [8] утверждают, что Пифагор научился математике у вавилонян. Гораздо более ранние источники [9] утверждают, что Фалес и Пифагор путешествовали и учились в Египте .
В девятой книге « Начал» Евклида предложения 21–34, весьма вероятно, навеяны пифагорейскими учениями ; [10] это очень простой материал («нечетное, умноженное на четное, есть четное», «если нечетное число измеряет [= делит] четное число, то оно также измеряет [= делит] его половину»), но этого достаточно, чтобы доказать, что оно иррационально . [ 11] Пифагорейские мистики придавали большое значение четному и нечетному. [12] Открытие того, что число иррационально, приписывают ранним пифагорейцам (до Феодора ). [13] Раскрыв (говоря современным языком), что числа могут быть иррациональными, это открытие, по-видимому, спровоцировало первый фундаментальный кризис в истории математики; его доказательство или его обнародование иногда приписывают Гиппасу , который был изгнан или откололся от пифагорейской секты. [14] Это заставило провести различие между числами (целыми и рациональными — предметами арифметики), с одной стороны, и длинами и пропорциями (которые можно отождествить с действительными числами, рациональными или нет), с другой стороны.
Пифагорейская традиция также говорила о так называемых многоугольных или фигурных числах . [15] В то время как квадратные числа , кубические числа и т. д. сейчас считаются более естественными, чем треугольные числа , пятиугольные числа и т. д., изучение сумм треугольных и пятиугольных чисел оказалось плодотворным в ранний современный период (с XVII по начало XIX вв.).
Китайская теорема об остатках появляется как упражнение [16] в Sunzi Suanjing (3-й, 4-й или 5-й век н. э.). [17] (В решении Sunzi есть один важный шаг, опущенный: [примечание 4] это та проблема, которая была позже решена Kuṭṭaka Арьябхаты – см. ниже.) Результат был позже обобщен с помощью полного решения, называемого Da-yan-shu (大衍術) в Mathematical Treatise in Nine Sections Цинь Цзюшао 1247 года [18], который был переведен на английский язык в начале 19-го века британским миссионером Александром Уайли . [19]
В китайской математике также присутствует некоторый числовой мистицизм [примечание 5], но, в отличие от пифагорейцев, он, похоже, ни к чему не привел.
За исключением нескольких фрагментов, математика классической Греции известна нам либо по сообщениям современных ей нематематиков, либо по математическим работам раннего эллинистического периода . [20] В случае теории чисел это, в общем и целом, означает Платона и Евклида соответственно.
Хотя азиатская математика оказала влияние на греческое и эллинистическое образование, по-видимому, греческая математика также является местной традицией.
Евсевий , PE X, глава 4 упоминает Пифагора :
«В действительности, упомянутый Пифагор, усердно изучая мудрость каждого народа, посетил Вавилон, Египет и всю Персию, обучаясь у магов и жрецов; и в дополнение к ним он, как сообщается, учился у брахманов (это индийские философы); и от одних он почерпнул астрологию, от других геометрию, арифметику и музыку от третьих, и различные вещи от разных народов, и только от мудрецов Греции он ничего не получил, поскольку они были преданы нищете и недостатку мудрости; так что, напротив, он сам стал автором наставлений для греков в учении, которое он приобрел из-за границы». [21]
Аристотель утверждал, что философия Платона тесно связана с учениями пифагорейцев [22], и Цицерон повторяет это утверждение: Platonem ferunt didicisse Pythagorea omnia («Говорят, Платон изучил все пифагорейское»). [23]
Платон живо интересовался математикой и четко различал арифметику и вычисления. (Под арифметикой он подразумевал, в частности, теоретизирование о числе, а не то, что арифметика или теория чисел стали означать.) Именно из одного из диалогов Платона, а именно « Теэтет », известно, что Феодор доказал, что являются иррациональными. Теэтет был, как и Платон, учеником Феодора; он работал над различением различных видов несоизмеримых величин и, таким образом, был, возможно, пионером в изучении числовых систем . (Книга X « Начал» Евклида описывается Паппом как в значительной степени основанная на работе Теэтета.)
Евклид посвятил часть своих «Начал» простым числам и делимости — темам, которые однозначно относятся к теории чисел и являются для нее основными (книги VII–IX « Начал » Евклида ). В частности, он дал алгоритм вычисления наибольшего общего делителя двух чисел ( алгоритм Евклида ; «Начала» , предложение VII.2) и первое известное доказательство бесконечности простых чисел ( «Начала» , предложение IX.20).
В 1773 году Лессинг опубликовал эпиграмму, которую он нашел в рукописи во время своей работы библиотекарем; в ней утверждалось, что это письмо, отправленное Архимедом Эратосфену . [24] [25] Эпиграмма предлагала то, что стало известно как задача Архимеда о скоте ; ее решение (отсутствующее в рукописи) требует решения неопределенного квадратного уравнения (которое сводится к тому, что позже будет неправильно названо уравнением Пелля ). Насколько известно, такие уравнения впервые были успешно рассмотрены индийской школой. Неизвестно, имел ли сам Архимед метод решения.
О Диофанте Александрийском известно очень мало ; он, вероятно, жил в третьем веке нашей эры, то есть примерно через пятьсот лет после Евклида. Шесть из тринадцати книг « Арифметики » Диофанта сохранились в греческом оригинале, а еще четыре — в арабском переводе. « Арифметика» представляет собой сборник решенных задач, где задача неизменно состоит в нахождении рациональных решений системы полиномиальных уравнений, обычно вида или . Таким образом, в настоящее время диофантовы уравнения — это полиномиальные уравнения , для которых ищутся рациональные или целочисленные решения.
Хотя греческая астрономия, вероятно, оказала влияние на индийское образование , вплоть до введения тригонометрии [26], похоже, что индийская математика в остальном является местной традицией; [27] в частности, нет никаких доказательств того, что «Начала» Евклида достигли Индии до XVIII века. [28]
Арьябхата (476–550 гг. н. э.) показал, что пары одновременных сравнений можно решить методом, который он назвал куттака, или распылитель; [ 29 ] это процедура , близкая к (обобщению) алгоритму Евклида, который, вероятно, был открыт независимо в Индии. [30] Арьябхата, по-видимому, имел в виду приложения к астрономическим расчетам. [26]
Брахмагупта (628 г. н. э.) начал систематическое изучение неопределенных квадратных уравнений, в частности, неправильно названного уравнения Пелля , которым, возможно, первым заинтересовался Архимед , и которое не решалось на Западе до времен Ферма и Эйлера. Позже санскритские авторы последовали его примеру, используя техническую терминологию Брахмагупты. Общая процедура (чакравала , или «циклический метод») для решения уравнения Пелля была наконец найдена Джаядевой (цитируется в одиннадцатом веке; его работа в остальном утеряна); самое раннее сохранившееся изложение появляется в «Биджа-ганите» Бхаскары II (двенадцатый век). [31]
Индийская математика оставалась практически неизвестной в Европе до конца восемнадцатого века; [32] Работа Брахмагупты и Бхаскары была переведена на английский язык в 1817 году Генри Колбруком . [33]
В начале девятого века халиф Аль-Мамун заказал переводы многих греческих математических трудов и по крайней мере одного санскритского труда ( Синдхинд , который может [34] быть или не быть [35] Брахма -Пхутасиддхантой Брахмагупты ). Главный труд Диофанта, Арифметика , был переведен на арабский язык Кустой ибн Лукой (820–912). Часть трактата Аль-Фахри ( аль-Караджи , 953 – ок. 1029) в некоторой степени основывается на нем. По словам Рашеда Рошди, современник Аль-Караджи Ибн аль-Хайтам знал [36] то, что позже назовут теоремой Вильсона .
За исключением трактата о квадратах в арифметической прогрессии Фибоначчи , который путешествовал и учился в Северной Африке и Константинополе, в Западной Европе в Средние века не было никакой теории чисел, о которой стоило бы говорить. Ситуация начала меняться в Европе в конце Ренессанса , благодаря возобновленному изучению трудов греческой античности. Катализатором послужило текстовое исправление и перевод на латынь « Арифметики » Диофанта . [37]
Пьер де Ферма (1607–1665) никогда не публиковал свои труды; в частности, его работа по теории чисел содержится почти полностью в письмах к математикам и в частных заметках на полях. [38] В своих заметках и письмах он почти не приводил никаких доказательств — у него не было образцов в этой области. [39]
За свою жизнь Ферма внес следующий вклад в эту область:
Интерес Леонарда Эйлера (1707–1783) к теории чисел впервые возник в 1729 году, когда его друг, любитель [примечание 8] Гольдбах , указал ему на некоторые работы Ферма по этой теме. [50] [51] Это было названо «возрождением» современной теории чисел, [52] после относительного отсутствия успеха Ферма в привлечении внимания своих современников к этой теме. [53] Работы Эйлера по теории чисел включают следующее: [54]
Жозеф-Луи Лагранж (1736–1813) был первым, кто дал полные доказательства некоторых работ и наблюдений Ферма и Эйлера, например, теоремы о четырех квадратах и базовой теории ошибочно названного «уравнения Пелля» (для которого алгоритмическое решение было найдено Ферма и его современниками, а также Джаядевой и Бхаскарой II до них). Он также изучал квадратичные формы в полной общности (в отличие от ), определяя их отношение эквивалентности, показывая, как привести их к редуцированной форме и т. д.
Адриен-Мари Лежандр (1752–1833) был первым, кто сформулировал закон квадратичной взаимности. Он также предположил, что равносильно теореме о простых числах и теореме Дирихле об арифметических прогрессиях . Он дал полную трактовку уравнения [66] и работал над квадратичными формами в соответствии с направлениями, позднее полностью развитыми Гауссом. [67] В старости он был первым, кто доказал Великую теорему Ферма для (завершив работу Петера Густава Лежена Дирихле и указав как его, так и Софи Жермен ). [68]
В своих Disquisitiones Arithmeticae (1798) Карл Фридрих Гаусс (1777–1855) доказал закон квадратичной взаимности и разработал теорию квадратичных форм (в частности, определив их композицию). Он также ввел некоторые основные обозначения ( сравнения ) и посвятил раздел вычислительным вопросам, включая тесты на простоту. [69] Последний раздел Disquisitiones установил связь между корнями из единицы и теорией чисел:
Теория деления круга..., которая рассматривается в разделе 7, сама по себе не принадлежит арифметике, но ее принципы могут быть извлечены только из высшей арифметики. [70]
Таким образом, Гаусс, возможно, сделал первый шаг как к работам Эвариста Галуа , так и к алгебраической теории чисел .
Начиная с начала девятнадцатого века постепенно происходили следующие события:
Можно сказать, что алгебраическая теория чисел началась с изучения взаимности и циклотомии , но по-настоящему обрела себя с развитием абстрактной алгебры и ранней теории идеалов и теории оценок ; см. ниже. Общепринятой отправной точкой для аналитической теории чисел является теорема Дирихле об арифметических прогрессиях (1837), [72] [73], доказательство которой ввело L-функции и включало некоторый асимптотический анализ и предельный процесс на действительной переменной. [74] Первое использование аналитических идей в теории чисел фактически восходит к Эйлеру (1730-е годы), [75] [76], который использовал формальные степенные ряды и нестрогие (или неявные) предельные аргументы. Использование комплексного анализа в теории чисел началось позже: работа Бернхарда Римана (1859) о дзета-функции является канонической отправной точкой; [77] Теорема Якоби о четырех квадратах (1839), которая предшествовала ей, принадлежит к изначально другому направлению, которое к настоящему времени заняло ведущую роль в аналитической теории чисел ( модулярные формы ). [78]
История каждого подполя кратко рассматривается в его собственном разделе ниже; см. основную статью каждого подполя для более полного рассмотрения. Многие из наиболее интересных вопросов в каждой области остаются открытыми и активно прорабатываются.
Термин элементарный обычно обозначает метод, который не использует комплексный анализ . Например, теорема о простых числах была впервые доказана с использованием комплексного анализа в 1896 году, но элементарное доказательство было найдено только в 1949 году Эрдёшем и Сельбергом . [ 79] Термин несколько двусмыслен: например, доказательства, основанные на комплексных тауберовых теоремах (например, Винера–Икехары ), часто рассматриваются как весьма поучительные, но не элементарные, несмотря на использование анализа Фурье , а не комплексного анализа как такового. Здесь, как и везде, элементарное доказательство может быть длиннее и сложнее для большинства читателей, чем неэлементарное.
Теория чисел имеет репутацию области, многие результаты которой могут быть изложены неспециалисту. В то же время доказательства этих результатов не особенно доступны, отчасти потому, что диапазон инструментов, которые они используют, если что-то и есть, необычайно широк в математике. [80]
Аналитическая теория чисел может быть определена
Некоторые предметы, которые обычно считаются частью аналитической теории чисел, например, теория решета [примечание 9], лучше охватываются вторым, а не первым определением: некоторые из теорий решета, например, используют мало анализа [примечание 10], тем не менее, они относятся к аналитической теории чисел.
Ниже приведены примеры проблем в аналитической теории чисел: теорема о простых числах , гипотеза Гольдбаха (или гипотеза о близнецах-простых числах , или гипотезы Харди–Литтлвуда ), проблема Варинга и гипотеза Римана . Некоторые из наиболее важных инструментов аналитической теории чисел — это метод круга , методы решета и L-функции (или, скорее, изучение их свойств). Теория модулярных форм (и, в более общем смысле, автоморфных форм ) также занимает все более центральное место в инструментарии аналитической теории чисел. [82]
Можно задавать аналитические вопросы об алгебраических числах и использовать аналитические средства для ответа на такие вопросы; таким образом, алгебраическая и аналитическая теории чисел пересекаются. Например, можно определить простые идеалы (обобщения простых чисел в области алгебраических чисел) и спросить, сколько существует простых идеалов до определенного размера. На этот вопрос можно ответить с помощью исследования дзета-функций Дедекинда , которые являются обобщениями дзета-функции Римана , ключевого аналитического объекта в корнях предмета. [83] Это пример общей процедуры в аналитической теории чисел: вывод информации о распределении последовательности ( здесь, простых идеалов или простых чисел) из аналитического поведения соответствующим образом построенной комплекснозначной функции. [84]
Алгебраическое число — это любое комплексное число , которое является решением некоторого полиномиального уравнения с рациональными коэффициентами; например, каждое решение ( скажем) является алгебраическим числом. Поля алгебраических чисел также называются полями алгебраических чисел или коротко числовыми полями . Алгебраическая теория чисел изучает поля алгебраических чисел. [85] Таким образом, аналитическая и алгебраическая теория чисел могут пересекаться и пересекаются: первая определяется своими методами, вторая — своими объектами изучения.
Можно утверждать, что простейший вид числовых полей (а именно, квадратичные поля) уже изучался Гауссом, поскольку обсуждение квадратичных форм в Disquisitiones arithmeticae можно переформулировать в терминах идеалов и норм в квадратичных полях. ( Квадратичное поле состоит из всех чисел вида , где и являются рациональными числами, а является фиксированным рациональным числом, квадратный корень которого не является рациональным.) Если на то пошло, метод чакравала 11-го века сводится — в современных терминах — к алгоритму нахождения единиц действительного квадратичного числового поля. Однако ни Бхаскара, ни Гаусс не знали числовых полей как таковых.
Основы предмета были заложены в конце девятнадцатого века, когда были введены идеальные числа , теория идеалов и теория оценок ; это три взаимодополняющих способа решения проблемы отсутствия однозначной факторизации в полях алгебраических чисел. (Например, в поле, порожденном рациональными числами и , число может быть факторизовано как и ; все из , , и являются неприводимыми и, таким образом, в наивном смысле, аналогичны простым числам среди целых чисел.) Первоначальный импульс к развитию идеальных чисел (Куммером ) , по-видимому, пришел из изучения высших законов взаимности, [86], то есть обобщений квадратичной взаимности .
Числовые поля часто изучаются как расширения меньших числовых полей: поле L называется расширением поля K , если L содержит K. (Например, комплексные числа C являются расширением действительных чисел R , а действительные числа R являются расширением рациональных чисел Q. ) Классификация возможных расширений данного числового поля является сложной и частично открытой проблемой. Абелевы расширения — то есть расширения L поля K, такие, что группа Галуа [примечание 11] Gal( L / K ) поля L над K является абелевой группой — относительно хорошо изучены. Их классификация была объектом программы теории полей классов , которая была начата в конце 19 века (частично Кронекером и Эйзенштейном ) и в основном проводилась в 1900–1950 годах.
Примером активной области исследований в алгебраической теории чисел является теория Ивасавы . Программа Ленглендса , один из основных текущих крупномасштабных исследовательских планов в математике, иногда описывается как попытка обобщить теорию полей классов на неабелевы расширения числовых полей.
Центральная проблема диофантовой геометрии — определить, когда диофантово уравнение имеет решения, и если да, то сколько. Принятый подход заключается в том, чтобы рассматривать решения уравнения как геометрический объект.
Например, уравнение с двумя переменными определяет кривую на плоскости. В более общем смысле, уравнение или система уравнений с двумя или более переменными определяет кривую , поверхность или какой-либо другой подобный объект в n -мерном пространстве. В диофантовой геометрии спрашивается, есть ли какие-либо рациональные точки (точки, все координаты которых являются рациональными числами) или целые точки (точки, все координаты которых являются целыми числами) на кривой или поверхности. Если такие точки есть, следующим шагом будет спросить, сколько их и как они распределены. Основной вопрос в этом направлении заключается в том, есть ли конечное или бесконечное число рациональных точек на данной кривой или поверхности.
Пример здесь может быть полезен. Рассмотрим уравнение Пифагора, и мы хотели бы узнать его рациональные решения; то есть такие его решения, что x и y оба рациональны. Это то же самое, что запросить все целочисленные решения для ; любое решение последнего уравнения дает нам решение , для первого. Это также то же самое, что запросить все точки с рациональными координатами на кривой, описанной (окружностью радиуса 1 с центром в начале координат).
Перефразирование вопросов об уравнениях в терминах точек на кривых удачно. Конечность или нет числа рациональных или целых точек на алгебраической кривой (то есть рациональных или целых решений уравнения , где — многочлен от двух переменных) решающим образом зависит от рода кривой. [примечание 12] Главным достижением этого подхода является доказательство Уайлсом Великой теоремы Ферма , для которой другие геометрические понятия столь же важны.
Существует также тесно связанная область диофантовых приближений : дано число , определить, насколько хорошо оно может быть приближено рациональными числами. Ищутся приближения, которые хороши относительно количества места, необходимого для записи рационального числа: назвать (с ) хорошим приближением к , если , где велико. Этот вопрос представляет особый интерес, если является алгебраическим числом. Если не может быть приближено хорошо, то некоторые уравнения не имеют целочисленных или рациональных решений. Более того, несколько понятий (особенно понятие высоты ) являются критическими как в диофантовой геометрии, так и в изучении диофантовых приближений. Этот вопрос также представляет особый интерес в теории трансцендентных чисел : если число может быть приближено лучше, чем любое алгебраическое число, то оно является трансцендентным числом . Именно с помощью этого аргумента было показано, что π и e являются трансцендентными.
Диофантову геометрию не следует путать с геометрией чисел , которая представляет собой набор графических методов для ответа на некоторые вопросы алгебраической теории чисел. Арифметическая геометрия , однако, является современным термином для обозначения почти той же области, что и та, которая охватывается термином Диофантова геометрия . Термин арифметическая геометрия, возможно, чаще всего используется, когда кто-то хочет подчеркнуть связь с современной алгебраической геометрией (например, в теореме Фальтингса ), а не с методами диофантовых приближений.
Области, перечисленные ниже, датируются не ранее середины двадцатого века, даже если они основаны на более старом материале. Например, как объясняется ниже, алгоритмы в теории чисел имеют долгую историю, возможно, предшествовавшую формальной концепции доказательства. Однако современное изучение вычислимости началось только в 1930-х и 1940-х годах, в то время как теория вычислительной сложности появилась в 1970-х годах.
Вероятностная теория чисел начинается с вопросов, таких как следующие: Возьмем случайное целое число n от одного до миллиона. Насколько вероятно, что оно будет простым? (это просто другой способ спросить, сколько простых чисел находится между одним и миллионом). Сколько простых делителей будет у n в среднем? Какова вероятность того, что у него будет намного больше или намного меньше делителей или простых делителей, чем в среднем?
Большая часть вероятностной теории чисел может рассматриваться как важный частный случай изучения переменных, которые почти, но не совсем, взаимно независимы . Например, событие, что случайное целое число от одного до миллиона делится на два, и событие, что оно делится на три, почти независимы, но не совсем.
Иногда говорят, что вероятностная комбинаторика использует тот факт, что все, что происходит с вероятностью большей, чем должно иногда происходить; можно с такой же справедливостью сказать, что многие приложения вероятностной теории чисел опираются на тот факт, что все необычное должно быть редким. Если можно показать, что определенные алгебраические объекты (скажем, рациональные или целочисленные решения определенных уравнений) находятся в хвосте определенных разумно определенных распределений, то из этого следует, что их должно быть немного; это очень конкретное невероятностное утверждение, вытекающее из вероятностного.
Иногда нестрогий, вероятностный подход приводит к ряду эвристических алгоритмов и открытых проблем, в частности к гипотезе Крамера .
Арифметическая комбинаторика начинается с вопросов, подобных следующим: содержит ли достаточно «толстое» бесконечное множество много элементов в арифметической прогрессии: , , скажем? Можно ли записать большие целые числа в виде суммы элементов ?
Эти вопросы характерны для арифметической комбинаторики . Это в настоящее время объединяющаяся область; она включает в себя аддитивную теорию чисел (которая занимается некоторыми весьма специфическими множествами арифметической значимости, такими как простые числа или квадраты) и, возможно, часть геометрии чисел , вместе с некоторыми быстро развивающимися новыми материалами. Ее сосредоточенность на вопросах роста и распределения частично объясняет ее развивающиеся связи с эргодической теорией , теорией конечных групп , теорией моделей и другими областями. Термин аддитивная комбинаторика также используется; однако изучаемые множества не обязательно должны быть множествами целых чисел, а скорее подмножествами некоммутативных групп , для которых традиционно используется символ умножения, а не символ сложения; они также могут быть подмножествами колец , и в этом случае рост и · можно сравнить.
Хотя само слово «алгоритм» восходит лишь к некоторым читателям аль-Хорезми , тщательные описания методов решения старше доказательств: такие методы (то есть алгоритмы) так же стары, как и любая известная математика — древнеегипетская, вавилонская, ведическая, китайская, — тогда как доказательства появились только у греков классического периода.
Ранним случаем является то, что сейчас называется алгоритмом Евклида. В своей базовой форме (а именно, как алгоритм для вычисления наибольшего общего делителя ) он появляется как Предложение 2 Книги VII в Элементах , вместе с доказательством правильности. Однако в форме, которая часто используется в теории чисел (а именно, как алгоритм для нахождения целочисленных решений уравнения , или, что то же самое, для нахождения величин, существование которых гарантируется китайской теоремой об остатках ), он впервые появляется в работах Арьябхаты (V–VI вв. н. э.) как алгоритм, называемый kuṭṭaka («распылитель»), без доказательства правильности.
Есть два основных вопроса: «Можно ли это вычислить?» и «Можно ли это вычислить быстро?» Любой может проверить, является ли число простым, или, если это не так, разложить его на простые множители; сделать это быстро — другой вопрос. Быстрые алгоритмы для проверки простоты сейчас известны, но, несмотря на большую работу (как теоретическую, так и практическую), по-настоящему быстрого алгоритма для факторизации не существует.
Сложность вычисления может быть полезной: современные протоколы шифрования сообщений (например, RSA ) зависят от функций, которые известны всем, но чьи обратные известны лишь избранным, и потребовалось бы слишком много времени, чтобы разобраться в них самостоятельно. Например, эти функции могут быть такими, что их обратные можно вычислить только при факторизации определенных больших целых чисел. Хотя известно множество сложных вычислительных задач за пределами теории чисел, большинство работающих протоколов шифрования в настоящее время основаны на сложности нескольких задач теории чисел.
Некоторые вещи могут быть вообще невычислимы; на самом деле, это может быть доказано в некоторых случаях. Например, в 1970 году было доказано, как решение десятой проблемы Гильберта , что не существует машины Тьюринга , которая может решить все диофантовы уравнения. [87] В частности, это означает, что при заданном вычислимо перечислимом наборе аксиом существуют диофантовы уравнения, для которых нет доказательства, начиная с аксиом, того, имеет ли набор уравнений целочисленные решения или нет. (т. е. диофантовы уравнения, для которых нет целочисленных решений, поскольку при заданном диофантовом уравнении с по крайней мере одним решением само решение обеспечивает доказательство того факта, что решение существует. Невозможно доказать, что конкретное диофантово уравнение относится к этому виду, поскольку это означало бы, что у него нет решений.)
Теоретик чисел Леонард Диксон (1874–1954) сказал: «Слава богу, что теория чисел не запятнана никакими приложениями». Такой взгляд больше не применим к теории чисел. [88] В 1974 году Дональд Кнут сказал: «практически каждая теорема в элементарной теории чисел возникает естественным, мотивированным образом в связи с проблемой создания компьютеров, выполняющих высокоскоростные числовые вычисления». [89] Элементарная теория чисел преподается на курсах дискретной математики для компьютерных специалистов . Она также имеет приложения к непрерывному численному анализу . [90]
Теория чисел в настоящее время имеет несколько современных приложений, охватывающих различные области, такие как:
Американское математическое общество присуждает премию Коула по теории чисел . Более того, теория чисел является одной из трех математических дисциплин, награждаемых премией Ферма .
[...] вопрос «как была рассчитана табличка?» не обязательно должен иметь тот же ответ, что и вопрос «какие задачи решает табличка?» На первый вопрос можно ответить наиболее удовлетворительно с помощью взаимных пар, как впервые было предложено полвека назад, а на второй — с помощью неких задач на прямоугольные треугольники (Робсон 2001, стр. 202).
Робсон не согласен с мнением, что писец, создавший Plimpton 322 (который должен был «работать, чтобы прокормиться», и не принадлежал к «праздному среднему классу»), мог быть мотивирован собственным «праздным любопытством» в отсутствие «рынка для новой математики» (Робсон 2001, стр. 199–200).
[26] Теперь есть неизвестное количество вещей. Если мы считаем по три, то остаток 2; если мы считаем по пять, то остаток 3; если мы считаем по семь, то остаток 2. Найдите количество вещей. Ответ : 23.
Метод : Если мы считаем тройками и получаем остаток 2, запишите 140. Если мы считаем пятерками и получаем остаток 3, запишите 63. Если мы считаем семерками и получаем остаток 2, запишите 30. Сложите их, чтобы получить 233, и вычтите 210, чтобы получить ответ. Если мы считаем тройками и получаем остаток 1, запишите 70. Если мы считаем пятерками и получаем остаток 1, запишите 21. Если мы считаем семерками и получаем остаток 1, запишите 15. Когда [число] превышает 106, результат получается путем вычитания 105.
[36] Беременная женщина, возраст которой 29 лет. Если срок беременности 9 месяцев, определите пол будущего ребенка. Ответ : мужской.
Метод : Запишите 49, добавьте период беременности и вычтите возраст. Из остатка вычтите 1, представляющий небо, 2 — землю, 3 — человека, 4 — четыре времени года, 5 — пять фаз, 6 — шесть камертонов, 7 — семь звезд [Ковша], 8 — восемь ветров и 9 — девять частей [Китая при Юе Великом]. Если остаток нечетный, [пол] мужской, а если остаток четный, [пол] женский.
Это последняя проблема в трактате Суньцзы, в остальном довольно сухом.
{{cite book}}
: CS1 maint: location missing publisher (link){{cite book}}
: CS1 maint: multiple names: authors list (link){{cite book}}
: CS1 maint: bot: original URL status unknown (link)Для других изданий см. Ямвлих#Список изданий и переводовДва самых популярных введения в эту тему:
Книга Харди и Райта является всеобъемлющей классикой, хотя ее ясность иногда страдает из-за настойчивости авторов на элементарных методах (Apostol 1981). Главная привлекательность Виноградова заключается в его наборе проблем, которые быстро приводят к собственным исследовательским интересам Виноградова; сам текст очень базовый и близок к минимальному. Другие популярные первые введения:
Популярные варианты второго учебника включают в себя: