# Number theory statements

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

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)$$
Property N.4: Upper and lower bounds for the value assumed by a function defined on integer numbers, by means of integrals of an extension

Let $f: I \rightarrow \mathbb{R}$ be a function defined on a set $I \subset \mathbb{Z}$.
Let $\overset{\sim}{f}: \overline{I} \rightarrow \mathbb{R}$ an extension of $f$, where $\overline{I} := \bigcup_{n \in I} [n, n + 1)$. Then:

• If $\overset{\sim}{f}$ is increasing, then $f(n) \leq \int_n^{n+1} \overset{\sim}{f}(t) dt$
• If $\overset{\sim}{f}$ is decreasing, then $f(n) \geq \int_n^{n+1} \overset{\sim}{f}(t) dt$

Let $\underset{\sim}{f}: \underline{I} \rightarrow \mathbb{R}$ be an extension of $f$, where $\underline{I} := \bigcup_{n \in I} (n - 1, n]$. Then:

• If $\underset{\sim}{f}$ is increasing, then $\int_{n-1}^n \underset{\sim}{f}(t) dt \leq f(n)$
• If $\underset{\sim}{f}$ is decreasing, then $\int_{n-1}^n \underset{\sim}{f}(t) dt \geq f(n)$
Lemma N.6: Order of magnitude of the sum of a fraction logarithms when the denominator changes $$\sum_{n=1}^x \log \left(\frac{x}{n} \right) = O(x)$$.