Введение
В математике постулат Бертрана (теперь теорема) утверждает, что для каждого *n* существует простое число *p* такое, что *n* < *p* < 2*n*. Впервые выдвинутый в 1845 году Жозефом Бертраном, он был впервые доказан Чебышевым, а более короткое, но также сложное доказательство было дано Рамануджаном. Следующее элементарное доказательство было опубликовано Полом Эрдошем в 1932 году, как одна из его первых математических работ. Основная идея заключается в том, чтобы показать, что центральные биномиальные коэффициенты должны иметь простой множитель в интервале (*n*/2, *n*) для того, чтобы быть достаточно большими. Это достигается путем анализа их разложения на множители. Основные этапы доказательства следующие. Во-первых, показывается, что вклад каждой простой степени *p* в разложение на простые множители центрального биномиального коэффициента не превышает log₂(*n*); затем показывается, что каждое простое число, большее чем √*n*, появляется в разложении не более одного раза. Следующий шаг – доказать, что не имеет простых множителей в интервале (*n*/2, *n*]. Как следствие этих ограничений, вклад в величину от простых множителей, не превышающих √*n*, растет асимптотически как *n*^(1/2) для некоторого *c*. Поскольку асимптотический рост центрального биномиального коэффициента составляет по крайней мере *c'* *n*^(1/2) (где *c'* – константа), то, по противоречию и для достаточно большого *n*, биномиальный коэффициент должен иметь другой простой множитель, который может лежать только между *n*/2 и *n*. Данный аргумент верен для всех *n*. Оставшиеся значения *n* проверяются непосредственным перебором, что завершает доказательство.
In mathematics, Bertrand's postulate (now a theorem) states that, for each , there is a prime such that First conjectured in 1845 by Joseph Bertrand, it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan. The following elementary proof was published by Paul Erdős in 1932, as one of his earliest mathematical publications. The basic idea is to show that the central binomial coefficients must have a prime factor within the interval in order to be large enough. This is achieved through analysis of their factorizations. The main steps of the proof are as follows. First, one shows that the contribution of every prime power factor in the prime decomposition of the central binomial coefficient is at most ; then, one shows that every prime larger than appears at most once. The next step is to prove that has no prime factors in the interval As a consequence of these bounds, the contribution to the size of coming from the prime factors that are at most grows asymptotically as for some Since the asymptotic growth of the central binomial coefficient is at least , the conclusion is that, by contradiction and for large enough , the binomial coefficient must have another prime factor, which can only lie between and
The argument given is valid for all The remaining values of are by direct inspection, which completes the proof.
Леммы в доказательстве
В доказательстве используются следующие четыре леммы для установления фактов о простых числах, содержащихся в центральных биномиальных коэффициентах.