Теорема Евклида - это фундаментальное утверждение теории чисел, которое утверждает, что существует бесконечно много простых чисел. Впервые это доказал Евклид в своей работе « Элементы . Есть несколько доказательств теоремы.
Доказательство Евклида
Евклид представил доказательство, опубликованное в его работе « Элементы» (книга IX, предложение 20), [1], которое перефразировано здесь. [2]
Рассмотрим любой конечный список простых чисел p 1 , p 2 , ..., p n . Будет показано, что существует по крайней мере одно дополнительное простое число, которого нет в этом списке. Пусть P будет произведением всех простых чисел в списке: P = p 1 p 2 ... p n . Пусть q = P + 1. Тогда q либо простое, либо нет:
- Если q простое число, то в списке нет еще как минимум одного простого числа.
- Если q не простое число, то некоторый простой делитель p делит q . Если бы этот множитель p был в нашем списке, он бы разделил P (поскольку P является произведением каждого числа в списке); но p также делит P + 1 = q , как только что сказано. Если p делит P, а также q, то p также должно делить разность [3] двух чисел, которая равна ( P + 1) - P или просто 1. Поскольку никакое простое число не делит 1, p не может быть в списке. Это означает, что существует по крайней мере еще одно простое число помимо тех, что указаны в списке.
Это доказывает, что для каждого конечного списка простых чисел есть простое число, которого нет в списке. [4] В оригинальной работе, поскольку Евклид не имел возможности написать произвольный список простых чисел, он использовал метод, который он часто применял, то есть метод обобщаемого примера. А именно, он выбирает всего три простых числа и, используя общий метод, описанный выше, доказывает, что он всегда может найти дополнительное простое число. Евклид предположительно предполагает, что его читатели убеждены в том, что подобное доказательство будет работать независимо от того, сколько простых чисел выбрано изначально. [5]
Часто ошибочно сообщается, что Евклид доказал этот результат путем противоречия, начиная с предположения, что изначально рассматриваемое конечное множество содержит все простые числа [6], хотя на самом деле это доказательство по случаям , прямой метод доказательства . Философ Торкель Францен в своей книге по логике утверждает: «Доказательство Евклида, что существует бесконечно много простых чисел, не является косвенным доказательством [...] Этот аргумент иногда формулируется как косвенное доказательство, заменяя его предположением« Предположим, q 1 , ... q n - все простые числа. Однако, поскольку это предположение даже не используется в доказательстве, переформулировать бессмысленно ". [7]
Вариации
Существует несколько вариантов доказательства Евклида, в том числе следующие:
Факториала п ! положительного целого числа n делится на любое целое число от 2 до n , так как оно является произведением всех из них. Следовательно, n ! + 1 не делится ни на одно из целых чисел от 2 до n включительно (при делении на каждое из них получается остаток 1). Следовательно, n ! + 1 либо простое число, либо делится на простое число больше n . В любом случае для каждого натурального числа n существует хотя бы одно простое число больше n . Напрашивается вывод, что число простых чисел бесконечно. [8]
Доказательство Эйлера
Другое доказательство, сделанное швейцарским математиком Леонардом Эйлером , опирается на фундаментальную теорему арифметики : каждое целое число имеет уникальную факторизацию на простые множители. Если P - множество всех простых чисел, Эйлер писал, что:
Первое равенство дается формулой для геометрического ряда в каждом члене произведения. Второе равенство является частным случаем продукта Эйлера формулы для дзета - функции Римана . Чтобы показать это, распределите продукт по сумме:
В результате каждое произведение простых чисел появляется ровно один раз, и поэтому по основной теореме арифметики сумма равна сумме всех целых чисел.
Сумма справа - это расходящийся гармонический ряд . Таким образом, продукт слева также должен расходиться. Поскольку каждый член продукта конечен, количество членов должно быть бесконечным; следовательно, существует бесконечное количество простых чисел.
Доказательство Эрдеша
Пол Эрдеш дал доказательство [9], которое также опирается на основную теорему арифметики. Каждое положительное целое число имеет уникальную факторизацию в число без квадратов и квадратное число rs 2 . Например, 75 600 = 2 4 3 3 5 2 7 1 = 21 ⋅ 60 2 .
Пусть N быть положительным целым числом, и пусть к быть число простых чисел меньше или равно N . Назовите эти простые числа p 1 , ..., p k . Любое положительное целое число, меньшее или равное N, может быть записано в форме
где каждый e i равен 0 или 1 . Существует 2 k способов формирования бесквадратной части a . И ев 2 может быть не более чем N , так что с ≤ √ N . Таким образом, в таком виде можно записать не более 2 k √ N чисел. Другими словами,
Или, переставив k , количество простых чисел, меньшее или равное N , больше или равно1/2войти 2 N . Поскольку N было произвольным, k может быть сколь угодно большим, выбрав N соответствующим образом.
Доказательство Фюрстенберга
В 1950-х годах Хиллель Фюрстенберг ввел доказательство от противного, используя топологию точечных множеств . [10]
Определим топологию на целых Z , называется равномерно целым числом топологии , объявив подмножество U ⊆ Z , чтобы быть открытым множеством тогда и только тогда , когда оно является либо пустым множеством , ∅, или это объединение арифметического последовательности S ( a , b ) (при a ≠ 0), где
Тогда противоречие следует из свойства, что конечный набор целых чисел не может быть открытым, и свойства, что базисные множества S ( a , b ) одновременно открыты и замкнуты , поскольку
не может быть замкнутым, поскольку его дополнение конечно, но замкнутым, поскольку представляет собой конечное объединение замкнутых множеств.
Некоторые недавние доказательства
Доказательство с использованием принципа включения-исключения
Хуан Пабло Пинаско написал следующее доказательство. [11]
Пусть p 1 , ..., p N - наименьшие N простых чисел. Тогда по принципу включения-исключения количество натуральных чисел, меньших или равных x , которые делятся на одно из этих простых чисел, равно
Разделив на x и положив x → ∞, получим
Это можно записать как
Если не существует других простых чисел, кроме p 1 , ..., p N , то выражение в (1) равно и выражение в (2) равна 1, но очевидно , что выражение в (3) не равен 1. Таким образом, должно быть больше , чем простые числа р 1 , ..., р Н .
Доказательство с использованием формулы де Полиньяка
В 2010 году Чунхо Питер Ван опубликовал следующее доказательство от противного. [12] Пусть k - любое натуральное число. Затем по формуле де Полиньяка (на самом деле благодаря Лежандру )
где
Но если существует только конечное число простых чисел, то
(числитель дроби будет расти однократно экспоненциально, тогда как в приближении Стирлинга знаменатель растет быстрее, чем однократно экспоненциально), что противоречит тому факту, что для каждого k числитель больше или равен знаменателю.
Доказательство по построению
Филип Сайдак дал следующее доказательство по построению , которое не использует reductio ad absurdum [13] или лемму Евклида (что если простое число p делит ab, то оно должно делить a или b ).
Поскольку каждое натуральное число (> 1) имеет по меньшей мере один простой множитель , а два последовательного числа п и ( п + 1) не имеет коэффициента общих, продукт п ( п + 1) , имеют более различные простые множители , чем число п самого . Итак, цепочка пронических чисел :
1 × 2 = 2 {2}, 2 × 3 = 6 {2, 3}, 6 × 7 = 42 {2, 3, 7}, 42 × 43 = 1806 {2, 3, 7, 43}, 1806 × 1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
обеспечивает последовательность неограниченных растущих наборов простых чисел.
Доказательство с использованием иррациональности π
Представление формулы Лейбница для π в виде произведения Эйлера дает [14]
Числители этого произведения - нечетные простые числа, а каждый знаменатель кратен четырем ближайшим к числителю.
Если бы конечное число простых чисел эта формула будет показать , что тг является рациональным числом, знаменатель является произведением всех кратных 4, которые более или менее один , чем простое число, что противоречит тому , что π является иррациональным .
Доказательство с использованием теории информации
Александр Шен и другие [ кто? ] представили доказательство, использующее несжимаемость : [15]
Предположим, что было всего k простых чисел ( p 1 ... p k ). По основной теореме арифметики любое натуральное число n может быть представлено в виде:
где неотрицательные целые показатели e i вместе со списком простых чисел конечного размера достаточно для восстановления числа. Сдля всех i следует, что все (где обозначает логарифм по основанию 2).
Это дает кодировку для n следующего размера (с использованием большой нотации O ):
- биты.
Это гораздо более эффективное кодирование, чем представление n непосредственно в двоичном формате, которое требуетбиты. Установленный результат сжатия данных без потерь утверждает, что, как правило, невозможно сжать N бит информации до менее чем N бит. Приведенное выше представление явно нарушает это, когда n достаточно велико, так как.
Следовательно, количество простых чисел не должно быть конечным.
Более сильные результаты
Из теорем этого раздела одновременно следует теорема Евклида и другие результаты.
Теорема Дирихле об арифметических прогрессиях
Теорема Дирихле утверждает, что для любых двух положительных взаимно простых целых чисел a и d существует бесконечно много простых чисел вида a + nd , где n также является положительным целым числом. Другими словами, существует бесконечное множество простых чисел, которые сравнимы с с по модулю д .
Теорема о простых числах
Пусть π ( х ) является функция распределения простых чисел , что дает число простых чисел меньше или равно х , для любого вещественного числа х . Теорема простое число , то утверждает , что х / Журнал х является хорошим приближением к П ( х ) , в том смысле , что предел в фактор из двух функций л ( х ) и х / лог х в х неограниченно возрастает в 1 :
Используя асимптотические обозначения, этот результат можно переформулировать как
Отсюда следует теорема Евклида, поскольку
Теорема Бертрана – Чебышева.
В теории чисел , постулат Бертрана является теорема о том , что для любого целого числа , всегда существует хотя бы одно простое число такое, что
Теорема Бертрана – Чебышева также может быть сформулирована как связь с , где это основная функция подсчета (количество простых чисел меньше или равно):
- , для всех .
Это утверждение было впервые высказано в 1845 г. Джозефом Бертраном [16] (1822–1900). Сам Бертран проверил свое утверждение для всех чисел в интервале [2, 3 × 10 6 ]. Его гипотеза была полностью доказана на Чебышева (1821-1894) в 1852 году [17] , и поэтому постулата также называется теоремой Бертрана-Чебышева или теорема Чебышева .
Примечания и ссылки
- ^ Джеймс Уильямсон (переводчик и комментатор), Элементы Евклида, с диссертациями , Clarendon Press , Oxford, 1782, стр.
- ^ Ore, Oystein (1988) [1948], теория чисел и его история , Dover, стр. 65
- ^ В общем, для любых целых чисел a , b , c, если а также , тогда . Для получения дополнительной информации см. Делимость .
- ^ Точная формулировка утверждения Евклида такова: «Простые числа более многочисленны, чем любое предлагаемое множество простых чисел».
- ^ Кац, Виктор Дж. (1998), История математики / Введение (2-е изд.), Аддисон Уэсли Лонгман, стр. 87
- ^ Майкл Харди и Кэтрин Вудголд, "Prime Simplicity", Mathematical Intelligencer , том 31, номер 4, осень 2009 г., страницы 44–52.
- ^ Франзен, Торкель (2004), Неисчерпаемость: неполное рассмотрение , AK Peters, Ltd, стр. 101
- ^ Босток, Линда; Чендлер, Сюзанна; Рурк, К. (01.11.2014). Дальнейшая чистая математика . Нельсон Торнс. п. 168. ISBN 9780859501033.
- ^ Хэвил, Джулиан (2003). Гамма: изучение константы Эйлера . Издательство Принстонского университета. стр. 28 -29. ISBN 0-691-09983-9.
- ^ Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячник . 62 (5): 353. DOI : 10,2307 / 2307043 . JSTOR 2307043 . Руководство по ремонту 0068566 .
- ↑ Хуан Пабло Пинаско, «Новые доказательства теорем Евклида и Эйлера», American Mathematical Monthly , том 116, номер 2, февраль 2009 г., страницы 172–173.
- ^ Junho Питер Уанг, "Еще одно доказательство Бесконечность простых чисел", American Mathematical Monthly , объем 117, номер 2, февраль 2010, стр 181.
- ^ Саидак, Филип (декабрь 2006 г.). «Новое доказательство теоремы Евклида» . Американский математический ежемесячник . 113 (10). DOI : 10.2307 / 27642094 .
- ^ Дебнат, Локенат (2010), Наследие Леонарда Эйлера: дань трехсотлетия , World Scientific, стр. 214, ISBN 9781848165267.
- ^ Шен, Александр (2016), Колмогоровская сложность и алгоритмическая случайность (PDF) , AMS, стр. 245
- ^ Бертран, Жозеф (1845 г.), «Память о числах валерьянок, о которых идет речь, о том, что они делают, о том, что они переставляют летописи qu'elle renferme». , Journal de l'École Royale Polytechnique (на французском языке), 18 (Cahier 30): 123–140.
- ^ Чебычев, П. (1852 г.), «Воспоминания о премьерах номеров». (PDF) , Journal de mathématiques pures et appliquées , Серия 1 (на французском языке): 366–390. (Доказательство постулата: 371-382). См. Также Mémoires de l'Académie Impériale des Sciences de Saint Pétersbourg, vol. 7, стр. 15-33, 1854 г.
Внешние ссылки
- Вайсштейн, Эрик В. «Теорема Евклида» . MathWorld .
- Элементы Евклида, книга IX, предложение 20 (доказательство Евклида, на веб-сайте Дэвида Джойса в Университете Кларка)