Постулат Бертрана

Постулат Бертрана — это теорема теории чисел, утверждающая, что для любого натурального числа \(n > 1\) существует простое число \(p\), такое что \(n < p < 2n\). Постулат был сформулирован французским математиком Жозефом Луи Франсуа Бертраном в 1845 году на основе эмпирических наблюдений и впоследствии строго доказан Пафнутием Львовичем Чебышёвым в 1850 году. В честь доказательства Чебышёва постулат также называют теоремой Чебышёва о распределении простых чисел.

История

Формулировка Бертрана

В 1845 году французский математик Жозеф Бертран, занимаясь исследованием свойств простых чисел, выдвинул гипотезу: для любого целого числа \(n > 1\) между \(n\) и \(2n\) обязательно найдётся хотя бы одно простое число. Бертран проверил это утверждение для всех \(n\) до 3 000 000, но не смог найти общего доказательства. Его работа основывалась на эмпирических данных и не содержала строгого математического обоснования.

Доказательство Чебышёва

В 1850 году российский математик Пафнутий Чебышёв опубликовал первое строгое доказательство постулата Бертрана. Он использовал методы, связанные с гамма-функцией и свойствами биномиальных коэффициентов. Доказательство Чебышёва стало важным шагом в развитии аналитической теории чисел. В своей работе он показал, что для \(n \ge 2\) существует простое число между \(n\) и \(2n\), а для \(n = 1\) утверждение тривиально, так как \(2\) — простое число, и \(1 < 2 < 2\). Позднее доказательство было упрощено и адаптировано другими математиками, включая Пола Эрдёша, который в 1932 году предложил элементарное доказательство, не использующее сложных аналитических методов.

Дальнейшие обобщения

Постулат Бертрана послужил основой для ряда более общих теорем о распределении простых чисел. В частности, он является частным случаем теоремы о простых числах в арифметических прогрессиях и тесно связан с гипотезой Лежандра, которая утверждает, что между \(n^2\) и \((n+1)^2\) всегда есть простое число. Постулат также нашёл применение в комбинаторике и теории графов.

Формулировка и доказательство

Классическая формулировка

Для любого натурального числа \(n > 1\) существует простое число \(p\), удовлетворяющее неравенству: \[ n < p < 2n. \] Для \(n = 1\) утверждение также выполняется, так как \(2\) — простое число, и \(1 < 2 < 2\) (хотя строгое неравенство \(2 < 2\) не выполняется, обычно рассматривают \(n \ge 2\)).

Основные идеи доказательства Чебышёва

Доказательство Чебышёва опирается на анализ биномиального коэффициента \(\binom{2n}{n}\) и его делимости на простые числа. Ключевые шаги:

1. Рассматривается произведение всех простых чисел, не превышающих \(2n\).
2. Используется оценка величины \(\binom{2n}{n}\) через логарифмы.
3. Показывается, что если бы между \(n\) и \(2n\) не было простых чисел, то \(\binom{2n}{n}\) было бы слишком малым, что противоречит его фактическому значению.

Современное элементарное доказательство, предложенное Эрдёшем, использует лемму о том, что для \(n \ge 2\) произведение всех простых чисел, не превосходящих \(n\), не превышает \(4^n\).

Примеры

• Для \(n = 2\): между 2 и 4 есть простое число 3.
• Для \(n = 3\): между 3 и 6 есть простое число 5.
• Для \(n = 10\): между 10 и 20 есть простые числа 11, 13, 17, 19.
• Для \(n = 100\): между 100 и 200 есть 21 простое число, например 101, 103, 107, 109, 113 и т. д.

Применение

В теории чисел

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

В комбинаторике и теории графов

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

В криптографии

Постулат Бертрана важен для генерации больших простых чисел, используемых в криптосистемах с открытым ключом, таких как RSA. Гарантия наличия простого числа между \(n\) и \(2n\) позволяет эффективно искать простые числа заданного размера.

Связь с другими утверждениями

Теорема о простых числах

Постулат Бертрана является слабой формой теоремы о простых числах, которая описывает асимптотическое распределение простых чисел. Теорема утверждает, что количество простых чисел, не превосходящих \(x\), примерно равно \(x / \ln x\). Из неё следует, что для достаточно больших \(n\) интервал \((n, 2n)\) содержит примерно \(n / \ln n\) простых чисел, что значительно сильнее постулата Бертрана.

Гипотеза Лежандра

Гипотеза Лежандра, сформулированная в 1798 году, предполагает, что между \(n^2\) и \((n+1)^2\) всегда есть простое число. Эта гипотеза до сих пор не доказана и является более сильным утверждением, чем постулат Бертрана, поскольку интервал между квадратами чисел значительно уже, чем \((n, 2n)\).

Гипотеза Крамера

Гипотеза Крамера о распределении простых чисел предполагает, что максимальные промежутки между последовательными простыми числами растут как \(O(\ln^2 n)\). Постулат Бертрана гарантирует, что промежуток не превышает \(n\), что является гораздо более слабой оценкой.

Интересные факты

• Постулат Бертрана был доказан Чебышёвым, который также внёс значительный вклад в теорию вероятностей и математический анализ.
• В 1932 году венгерский математик Пол Эрдёш в возрасте 19 лет опубликовал элементарное доказательство постулата, которое стало его первой крупной работой.
• Утверждение постулата можно обобщить: для любого \(n \ge 1\) существует простое число между \(n\) и \(2n\) (за исключением тривиального случая \(n=1\), где \(2\) — простое число, но неравенство \(2 < 2\) нестрогое).
• Постулат используется для доказательства того, что последовательность простых чисел бесконечна: если бы простых чисел было конечное количество, то для достаточно большого \(n\) между \(n\) и \(2n\) не было бы простых чисел, что противоречит постулату.

Источники

• Бертран, Ж. Л. Ф. «Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu’elle renferme», 1845.
• Чебышёв, П. Л. «Sur la fonction qui détermine la totalité des nombres premiers inférieurs à une limite donnée», 1850.
• Эрдёш, П. «Beweis eines Satzes von Tschebyscheff», 1932.
• Харди, Г. Х., Райт, Э. М. «Введение в теорию чисел», 1938.
• Айерленд, К., Роузен, М. «Классическое введение в современную теорию чисел», 1982.