Number theory statements

A list of the statements appearing in our posts about number theory follows.

Title and link Statement
Theorem N.1: Fundamental theory of arithmetic (not proved) Every integer number greater than 1 can be written as a product of prime numbers. Moreover such expression, called factorization or decomposition into prime factors, is unique apart from the order of the factors.
Theorem N.2: Infinity of primes The number of primes is infinite.
Property N.1: Overestimation of binomials For all n > 0 and for all m: \binom{n}{m} \leq 2^{n-1}
Property N.2: Underestimation of the central binomials of the Pascal’s triangle For all n \geq 2: \binom{n}{\frac{n}{2}} \geq \frac{2^n}{n} if n is even, and \binom{n}{\left \lceil \frac{n}{2} \right \rceil} = \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor} \geq \frac{2^n}{n} if n is odd.
Property N.3: Underestimation of the central binomial of Pascal’s triangle, even n For all even n \geq 2: \binom{n}{\frac{n}{2}} \geq \sqrt{2^{n}}
Proposition N.1: Majorization of the product of primes up to x For all x > 0: \theta^{\star}(x) = \prod_{1 \leq p \leq x} p \leq 2^{2(x-1)}
Theorem N.3: Bertrand’s postulate For all n > 0, there exists a prime number between n + 1 and 2n.
Lemma N.1: Factorization of the binomial \binom{2n}{n} In the factorization of the binomial \binom{2n}{n}, for n > 0, a prime number p cannot have an exponent greater than \log_p 2n.
Proposition N.2: Computation of \psi^{\star}(x) For every integer x > 0: \psi^{\star}(x) = \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor}
Corollary of Proposition N.2: Overestimation of \psi^{\star}(x) with \pi(x) For every integer x > 0: \psi^{\star}(x) \leq x^{\pi(x)}
Proposition N.3: Underestimation of \psi^{\star}(x) For every integer x > 0: \psi^{\star}(x) \geq \sqrt[3]{2^x}
Lemma N.2: Reformulation of \psi^{\star}(x) (“calculation by rows”) For every integer x > 0: \psi^{\star}(x) = \left(\prod_{p \leq x} p\right) \cdot \left(\prod_{p^2 \leq x} p\right) \cdot \dots \cdot \left(\prod_{p^R \leq x} p\right)
Proposition N.4: Connection between \psi^{\star} and \theta^{\star} functions For every integer x > 0: \psi^{\star}(x) = \theta^{\star}(x) \cdot \theta^{\star}(\sqrt{x}) \cdot \dots \cdot \theta^{\star}(\sqrt[R]{x}), where R := \left \lfloor \log_2 x \right \rfloor.
Lemma N.3: Underestimation of \theta^{\star}(x) through \pi(x) For every real number \delta \geq 0 and for every x \gt 1: \theta^{\star}(x) \gt \left(x^{\delta}\right)^{\pi(x) - x^{\delta}}.
Theorem N.4: Asymptotic equivalence and order of magnitude of \theta(x) and \psi(x) The functions \theta(x) and \psi(x) are asymptotically equivalent and have order x: \theta(x) \sim \psi(x), \theta(x) \asymp x \asymp \psi(x).
Theorem N.5: Asymptotical equivalence between \pi(x) and \frac{\theta(x)}{\log x} \pi(x) \sim \frac{\theta(x)}{\log x}
Corollary of Theorem N.5: Asymptotical equivalence between \pi(x) and \frac{\psi(x)}{\log x} \pi(x) \sim \frac{\psi(x)}{\log x}
Corollary II of Theorem N.5: Chebyshev’s Theorem: order of magnitude of \pi(x) \pi(x) \asymp \frac{x}{\log x}
Lemma N.4: Lemma of bar chart area Let c_1, c_2, \dots, c_n be natural numbers, with n > 0. Let f: \{1, 2, ..., n\} \rightarrow \mathbb{R} be a function. Then the area A of the bar chart made up of n rectangles, each having basis c_i and height f(i), given by A = c_1 f(1) + c_2 f(2) + \ldots + c_n f(n) = \sum_{i=1}^{n} c_i f(i), can also be computed with the formula \begin{aligned}A &= C_n f(n) + C_{n-1} (f(n-1) - f(n)) + \ldots + C_1 (f(1) - f(2)) \\&= \sum_{k = 1}^{n-1} C_k (f(k) - f(k + 1)) + C_n f(n)\end{aligned} where C_k := c_1 + c_2 + \ldots + c_k = \sum_{i=1}^{k} c_i.
Lemma N.5: Lemma of bar chart area, second form Let c_1, c_2, \dots, c_n be natural numbers, with n > 0. Let f: \{1, 2, ..., n\} \rightarrow \mathbb{R} be a function, and \widetilde{f} a C^1 extension of f. Then the area A of the bar chart made up of n rectangles, each with basis c_i and height f(i), given by A = c_1 f(1) + c_2 f(2) + \ldots + c_n f(n) = \sum_{i=1}^{n} c_i f(i), can be also computed with the formula C(n) f(n) - \int_1^n \overline{C}(k) \widetilde{f}'(t) dt where C: \{1, 2, ..., n\} \rightarrow \mathbb{N} is the function defined by C(k) := c_1 + c_2 + \ldots + c_k = \sum_{i=1}^{k} c_i.
Theorem N.6: Approximation of the sum of inverses of the first positive integers

For all integers n \gt 0:

\sum_{k = 1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} \approx \log n + \gamma

where logarithm base is Napier’s number e, while \gamma \approx 0.58 is the Euler’s constant. In particular:

\sum_{k = 1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} = \log n + \gamma + O\left(\frac{1}{n}\right)