Если вы знаете только доказательство Евклида, вот несколько других, которыми вы можете произвести впечатление на своих друзей.
Одна из первых вещей, которую изучают большинство студентов-математиков (и, возможно, даже некоторые умные и увлеченные старшеклассники), - это доказательство того, что простых чисел бесконечно много. В большинстве случаев это классическое доказательство, разработанное греческим математиком Евклидом около 300 г. до н.э. и представленное в книге 9 его 13-томного трактата Элементы.
Неудивительно, что с тех пор, как Евклид опубликовал свое доказательство, прошло более 2000 лет, люди нашли другие подходы к доказательству того, что простых чисел бесконечно много. Некоторые из них представляют собой хитроумные способы переформулировать подход Евклида, а некоторые используют новые разделы математики, которых не существовало во времена Евклида.
Вот шесть способов доказать, что простых чисел бесконечно много. Мы начнем с классического доказательства Евклида и рассмотрим остальные в порядке их далеких от первоначального подхода Евклида.
1. Евклид (ок. 300 г. до н.э.): для любого конечного списка простых чисел есть по крайней мере одно простое число не в этом списке.
Для начала нам нужен простой подтверждающий результат:
Лемма 1.1: для любых трех целых чисел a, b и c, если a делит b и a делит c, затем a делит b﹣ c .
Доказательство: b = am для некоторого целого числа m и c = для некоторого целого числа n. Следовательно,
b﹣ c = am ﹣ an = a (m ﹣ n). Поскольку m ﹣ n явно целое число, a делит b ﹣ c.
Это все, что нам нужно для прекрасного доказательства Евклида.
Теорема 1.2: Если 𝓟 - конечный список простых чисел, существует простое число, не входящее в 𝓟.
Доказательство. Постройте число P как произведение всех простых чисел в списке 𝓟 и рассмотрите число P + 1. Если P +1 простое число, мы доказали теорему 1.2. Итак, предположим, что P +1 не простое число. Тогда P +1 делится на меньшее простое число p. Если p находится в нашем списке 𝓟, то p делит и P + 1, и P. По лемме 1.1 p должен также делить P + 1﹣ P,, поэтому p делит 1. Поскольку это невозможно, p не может быть в нашем списке 𝓟.
2. Эрмит (ок. 1860 г.): Для любого положительного целого числа существует большее простое число.
Это доказательство французского математика Шарля Эрмита, возможно, так же просто, как и подход Евклида.
Теорема 2.1: для любого целого n ›1 если p является простым делителем n! +1, затем p ›n. Следовательно, простых чисел бесконечно много.
Доказательство: если p ≤ n, тогда p делит n!. Но p также делит n! + 1, поэтому по лемме 1.1 p делит n! + 1 ﹣ п !. Итак, p делит 1, что не может быть правдой. Итак, п ›п.
3. Гольдбах (1730 г.): Существует бесконечно много простых чисел, потому что существует бесконечно много чисел Ферма.
Числа Ферма - это числа вида
Первые 4 числа Ферма - это 3, 5, 17, 257, и затем они довольно быстро становятся довольно большими.
Для начала нам нужен интересный результат о числах Ферма:
Лемма 3.1: для любого натурального числа m
Доказательство (по индукции):
Теперь мы можем доказать, что любая пара чисел Ферма взаимно проста, то есть у них нет общих простых множителей.
Лемма 3.2: Любая пара чисел Ферма взаимно проста.
Доказательство. Возьмем два числа Ферма Fᵤ ‹Fᵥ. Если бы у них обоих был общий простой множитель p, то по лемме 3.1 p делил бы Fᵥ и Fᵥ ﹣2. Следовательно, по лемме 1.1 p делит Fᵥ﹣ (Fᵥ ﹣2), поэтому p делит 2. Но поскольку простые числа Ферма явно нечетные числа, этого не может быть, и поэтому оба числа должны быть взаимно простыми.
Теперь это позволяет легко доказать основной результат.
Теорема 3.3: простых чисел бесконечно много.
Доказательство. Чисел Ферма бесконечно много, и каждое из них имеет разные простые множители, поэтому простых чисел бесконечно много.
Интересно отметить, что гипотеза Гольдбаха о простых числах - одна из простейших гипотез в теории чисел, которая остается нерешенной: в ней говорится, что любое четное число больше 2 может быть выражено как сумма двух простых чисел.
4. Филип Саидак (2005 г.): Вы можете построить бесконечное множество чисел, каждое из которых содержит новый простой множитель.
Это очень красивое доказательство, которое легко следует из некоторых наших предыдущих результатов.
Во-первых, один из фактов, присущих доказательству Евклида, заключается в том, что для любого положительного целого числа n › 1, n и n + 1 взаимно просты.
Теорема 4.1: простых чисел бесконечно много.
Доказательство. Пусть n будет положительным целым числом больше 1. Поскольку n и n + 1 взаимно просты, то n (n + 1) должно иметь как минимум два различных простых делителя. Точно так же n (n + 1) и n (n + 1) + 1 взаимно просты, поэтому n (n + 1) (n (n + 1 ) + 1) должен содержать не менее трех различных простых множителей. Это можно продолжать бесконечно.
5. Лагранж (c 1800 г.): если бы простых чисел было конечное число, теорема Лагранжа была бы противоречива.
С этого момента доказательства требуют некоторых знаний чистой математики на уровне бакалавриата.
Лагранж установил следующую важную теорему в области теории групп. доказательство чего можно найти здесь.
Теорема 5.1 (теорема Лагранжа): Порядок (мощность) любой подгруппы конечной мультипликативной группы G должен делить порядок G.
Прежде чем мы продолжим, небольшое напоминание о Поле Галуа GF [p].
Определение 5.2: для простого p, GF [p] - это конечное поле целых чисел по модулю p. Если мы удалим элемент 0 из GF [p], мы образуем мультипликативную группу GF [p] * порядка p ﹣ 1. Для элемента q из GF [p] * порядок подгруппы, сгенерированной q, является наименьшим значением k такое, что q ᵏ ≡ 1 по модулю p.
Пример 5.3: GF [5] * - мультипликативная группа, содержащая элементы 1, 2, 3, 4. Порядок 3 равен 4, так как 3⁴ = 81 1 по модулю 5.
Теорема 5.4: простых чисел бесконечно много.
Доказательство. Предположим, что простых чисел конечное число. Пусть p будет наибольшим простым числом, и рассмотрим число 2ᵖ ﹣1. Пусть q - простое число, которое делит 2ᵖ ﹣1. Тогда 2ᵖ ≡ 1 по модулю q. Поскольку p простое число, это означает, что элемент 2 имеет порядок p в группе GF [q] *. Итак, GF [q] * имеет подгруппу порядка p. Но порядок GF [q] * равен q ﹣ 1, поэтому по теореме 5.1 p должен делить q ﹣1. Итак, p ‹q, что противоречит нашему предположению.
6. Фюрстенберг (1955): Если бы было конечное число простых чисел, можно было бы построить невозможную топологию.
Этот наиболее удален от других и, вероятно, труднее всего понять, если вы никогда не изучали топологию, но это захватывающий взгляд на то, как топология может помочь нам в решении алгебраических и теоретико-числовых задач.
Давайте определим топологию целых чисел следующим образом:
Определение 6.1: Подмножество U является открытым множеством тогда и только тогда, когда оно является пустым множеством или объединением множеств вида S (a, б) где S (a, b) - арифметическая прогрессия в форме an + b для всех целых чисел n и для a ≠ 0 .
Пример 6.2. Все целые числа являются открытым набором в этой топологии, поскольку он принимает форму S (1, 0). Арифметическая прогрессия {…, -4, -1, 2, 5,…} является открытым набором в этой топологии, поскольку принимает форму S (3, 2).
Легко показать, что эта конструкция является допустимой топологией, поскольку она удовлетворяет трем аксиомам: пустое множество и множество всех целых чисел открыты, любое объединение открытых множеств открыто, и любое конечное пересечение открытых множеств открыто.
Теорема 6.3: простых чисел бесконечно много.
Доказательство. Рассмотрим топологию, определенную выше. Обратите внимание, что:
- В любой топологии дополнением открытого множества является замкнутое множество. В этой топологии конечное непустое множество не может быть открытым, потому что никакой S (a, b) не является конечным. Иначе говоря, в этой топологии дополнение конечного непустого множества не может быть замкнутым.
- Множества S (a, b) открыты по определению, но они также могут быть записаны как дополнение к открытым множествам следующим образом, и поэтому они являются как открытыми, так и закрытыми (закрытые множества):
Теперь, поскольку все целые числа, кроме -1 и 1, являются произведением простых чисел, мы можем заключить, что они должны входить в набор S (p, 0) для некоторого простого p, поэтому:
Множество слева является дополнением к конечному множеству {-1, 1} и по пункту 1 не может быть замкнуто. Теперь, если бы было конечное число простых чисел, правая часть была бы конечным объединением замкнутых множеств (по пункту 2) и, следовательно, была бы замкнутой. Это приводит к противоречию, поэтому простых чисел должно быть бесконечно много.
Я бывший математик, занимающийся наукой о данных. У меня не так много времени, чтобы написать о своей первой страсти, но когда я это сделаю, я надеюсь, что вам это понравится. Найдите меня в LinkedIn или Twitter. Также посетите мой блог на drkeithmcnulty.com.