- Постулат Бертрана
-
Постулат Бертрана, теорема Бертрана — Чебышева или теорема Чебышева гласит, что
Для любого натурального n ≥ 2 найдётся простое число p в интервале n < p < 2n.
Такая гипотеза была выдвинута в 1845 году французским математиком Бертраном (проверившим её до n=3000000) и доказана в 1850 году Чебышевым. Рамануджан в 1920 году нашёл более простое доказательство, а Эрдёш в 1932 году — ещё более простое.
Похожая, но недоказанная гипотеза Лежандра гласит, что для любого n ≥ 2 найдётся простое число p в интервале n2 < p < (n+1)2.
ДоказательствоЗдесь мы приводим доказательство, предложенное Эрдёшем.
Содержание
Обозначения и определения
В доказательстве мы используем следующие обозначения:
— биномиальный коэффициент или число сочетаний из a по b.
— целая часть x.
Обозначим множество простых чисел через
и определим θ(n) как сумму логарифмов простых чисел, не превышающих n:
Например,
.
Эта функция называется θ-функция Эрдёша.
Лемма
для всех
.
(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».)
Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного m, биноминальный коэффициент
делится на все простые числа в интервале [m+2, 2m+1]. В самом деле,
, a любое простое число в указанном интервале делит числитель этой дроби и не делит её знаменатель. А коль скоро биноминальный коэффициент делится на все такие простые числа, он не может быть меньше их произведения
Беря логарифм от обеих частей неравенства, получаем
С другой стороны, биноминальный коэффициент
легко оценить сверху:
-
.
Объединяя два последних неравенства, получаем
Откуда
Теперь легко доказать лемму по индукции:
- n = 1:
- n = 2:
- n > 2 и n чётно.
(здесь мы используем, что чётное число, большее 2 - составное и поэтому не входит в сумму
).
и n нечётно. Пусть n=2m+1.
Лемма доказана.
Доказательство основной теоремы
Теперь переходим к доказательству самого постулата. Основная идея доказательства - разложить биноминальный коэффициент
на простые множители. Если между n и 2n нет простых чисел, то произведение всех этих простых множителей окажется слишком маленьким.
Доказываем от противного. Допустим, что для некоторого целого n ≥ 2 не существует простого числа p такого, что n < p < 2n.
Если 2 ≤ n < 2048, то одно из простых чисел 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 и 2503 (каждое меньше удвоенного предыдущего), назовём его p, удовлетворяет неравенству n < p < 2n. Следовательно, n ≥ 2048.
Оценим
.
Поскольку
- максимальный член суммы, мы имеем:
Определение R(p,n) и его оценка сверху
Пускай
- степень p в разложении
на простые множители.
Поскольку n! для каждого j имеет ровно
сомножителей, делящихся на
, в разложении n! на простые множители p входит в степени
. Поэтому
Чтобы узнать об этой сумме побольше, оценим, с одной стороны, насколько велики её слагаемые, а с другой — их количество.
Величина: каждое слагаемое
может быть или 0, или 1 (в зависимости от дробной части
: если она меньше
, слагаемое равно 0, а если
или больше, то 1).
Количество: все слагаемые с
равны нулю, потому что для них
. Поэтому только
первых слагаемых имеют шансы быть ненулевыми.
Итак,
- сумма
слагаемых, каждое из которых равно 0 или 1. Следовательно,
Оценка
Оценим теперь
.
Это была оценка для любых p. Но гораздо лучшую оценку можно получить для
. Для таких p, количество слагаемых
равно 1, то есть в нашей, с позволения сказать, сумме всего одно слагаемое:
Если это слагаемое равно 1, то
. А если оно равно 0, то
.
В каком интервале могут находиться простые делители?
А теперь посмотрим, в каком интервале находятся простые делители.
не имеет простых делителей p таких, что:
- 2n < p, потому что
.
, потому что мы предположили, что в этом интервале нет простых чисел.
, потому что
(т.к.
), что даёт нам
.
Получается, что у
нет простых делителей, больших чем
.
Перемножение всех
Теперь оценим произведение
по всем простым делителям p числа
. Для делителей, не больших
, произведение не превышает
. А для простых делителей, больших
, оно не превышает
.
Поскольку
равен произведению
по всем простым p, мы получаем:
Используя нашу лемму
:
Поскольку
:
Кроме того,
(поскольку
):
Логарифмируя обе части, получаем
Делая подстановку 22t = 2n:
Это даёт нам t < 6 и противоречие:
Следовательно, наше допущение было неверно.
Категории:- Теория чисел
- Теоремы
- Доказательства
Wikimedia Foundation. 2010.