Number theory statements

The following is a list of the statements appearing in our posts about number theory.

Title and link Statement
Theorem N.1: Fundamental Theorem 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.
Property N.1A: Within natural numbers, a divisor is less than or equal to a positive dividend Let a and b be two natural numbers, with a \gt 0. If b \mid a, then b \leq a.
Property N.1B: Prime number, characteristic property or alternative definition A prime number is an integer number p > 1 such that, if p \mid bc, then p \mid b or p \mid c, for any integers b and c. In other terms, p cannot divide a product of integers bc without dividing at least one of the two 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 non-negative real 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 non-negative real 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)
Lemma N.6A: Order of magnitude of the sum of a fraction logarithms when the denominator changes, generalized form

Let h \in \mathbb{R}, h \gt 0. Then:

\sum_{n=1}^x \log \left(\frac{x}{n} \right) = O(x)

Proposition N.5: Order of magnitude of the factorial function x! = x^x \cdot e^{O(x)}
Property N.5: Number of multiples of a given number, between 1 and x

Let n and x be two positive integers. The number of multiples of n that belong to the range [1, x] is \left \lfloor \frac{x}{n} \right \rfloor.

Proposition N.6: The factorial function and the \Lambda^{\star} function For every integer x \gt 0: x! = \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor}
Property N.6: Connection between \Lambda^{\star} and \psi^{\star} For every integer x \gt 0: \prod_{r = 1}^x \Lambda^{\star}(r) = \psi^{\star}(x)
Proposition N.7: Order of magnitude of the factorial-like function based on \Lambda^{\star} \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}} = x^x \cdot e^{O(x)}
Corollary of Proposition N.7: Order of magnitude of the factorial-like function based on \Lambda^{\star} \sum_{r = 1}^x \frac{\Lambda(r)}{r} = \log x + O(1)
Theorem N.7: Limit inferior and limit superior of the function \frac{\overline{\psi}(t)}{t} \begin{cases} \lim \inf \frac{\overline{\psi}(t)}{t} \leq 1 \\ \lim \sup \frac{\overline{\psi}(t)}{t} \geq 1 \end{cases}
Corollary of Theorem N.7: Limit inferior and limit superior of the function \overline{\pi}(t) / \frac{t}{\log t} \begin{cases} \lim \inf \overline{\pi}(t) / \frac{t}{\log t} \leq 1 \\ \lim \sup \overline{\pi}(t) / \frac{t}{\log t} \geq 1 \end{cases}
Corollary II of Theorem N.7: Chebyshev’s Theorem, strong version If the function \pi(x) / \frac{x}{\log x} tends to a limit, that limit is 1.
Theorem N.8: Prime number Theorem \pi(x) \sim \frac{x}{\log x}
Theorem N.9: Prime number Theorem, strong version \pi(x) \sim \mathrm{Li}(x)
Lemma N.7: Sufficient condition for the validity of the Prime Number Theorem The following is a sufficient condition for the validity of the Prime Number Theorem:

\limsup_{x \to +\infty} |V(\log x)| = 0

where the function V is defined in Definition N.13.

Lemma N.8 Let x \gt 0 be a fixed integer. The following inequalities are equivalent:

  • |V(\log x)| \leq \frac{1}{\log x} \int_0^{\log x} |V(u)| du
  • \log x |R(x)| \leq \int_1^x \left|R\left(\frac{x}{t}\right)\right| dt
Theorem N.10: Selberg’s Theorem
R(x) \log x + \sum_{n = 1}^x \Lambda(n) R\left(\frac{x}{n}\right) = O(x)
Property N.7: Characterization of square-free integers An integer number is square-free if and only if in its factorization there are only distinct prime factors.
Property N.8: A property about the count of divisors of an integer greater than 1 Let n \gt 1 an integer number. Let E_n and O_n be the following sets:

E_n := \left\{ \begin{gathered} \text{square-free divisors of $n$,} \\ \text{which are a product of an even number of prime factors} \end{gathered}\right\}
O_n := \left\{ \begin{gathered} \text{square-free divisors of $n$,} \\ \text{which are a product of an odd number of prime factors} \end{gathered}\right\}

Then |E_n| = |O_n|.

Property N.9: A property about the product of divisors of a positive integer number with at least two distinct prime factors Let n be a positive integer numbr with at least two distinct prime factors. Let E_n and O_n be the sets defined in Property N.8. Then \prod_{a \in E_n} a = \prod_{b \in O_n} b.
Property N.9 (second form): A property about the product of divisors of a positive integer number with at least two distinct prime factors

Let n be a positive integer number with at least two distinct prime factors. Then:

\frac{\prod_{d \in P_n} d}{\prod_{d \in D_n} d} \cdot \prod_{d \in Q_n} d = \prod_{d \mid n} d^{\mu(d)} = 1
Property N.8 (second form): A property about the count of divisors of an integer greater than 1

Let n \gt 1 be an integer number. Then:

\sum_{d \mid n} \mu(d) = 0
Property N.10: A property about the product of divisors of a positive integer number

Let n \in \mathbb{N}^{\star}. Then:

\prod_{d \mid n} d^{\mu(d)} = \frac{1}{\Lambda^{\star}(n)}
Property N.10 (logarithmic form): A property about the product of divisors of a positive integer number

Let n \in \mathbb{N}^{\star}. Then:

\sum_{d \mid n} \mu(d) \log d = - \Lambda(n)
Property N.11: A property about the count of divisors of a positive integer number

Let n \in \mathbb{N}^{\star}. Then:

\sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{if $n = 1$} \\ 0 & \text{otherwise} \end{cases}
Property N.12: Expression of \Lambda^{\star} by means of \mu

Let n \in \mathbb{N}^{\star}. Then:

\prod_{d \mid n} \left( \frac{n}{d} \right)^{\mu(d)} = \Lambda^{\star}(n)
Property N.12 (logarithmic form): Expression of \Lambda by means of \mu

Let n \in \mathbb{N}^{\star}. Then:

\sum_{d \mid n} \mu(d) \log \frac{n}{d} = \Lambda(n)
Property N.13: Exchange between d and \frac{n}{d} in summations extended to the divisors of a positive integer

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{d \mid n} f\left(d, \frac{n}{d}\right) = \sum_{d \mid n} f\left(\frac{n}{d}, d\right)
\prod_{d \mid n} f\left(d, \frac{n}{d}\right) = \prod_{d \mid n} f\left(\frac{n}{d}, d\right)

(*) To be precise, it’s necessary that the operations of sum and product are defined on the codomain, and they must be commutative. However in this context there is no problem at all, because this is true for the numerical sets we are interested in, that are \mathbb{N}, \mathbb{Z} and \mathbb{R}.

Property N.14: Equivalent form for summations with d and \frac{n}{d}

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{d \mid n} f\left(d, \frac{n}{d}\right) = \sum_{ab = n} f(a,b)
\prod_{d \mid n} f\left(d, \frac{n}{d}\right) = \prod_{ab = n} f(a,b)

(*) To be precise, it’s necessary that the operations of sum and product are defined on the codomain, and they must be commutative. However in this context there is no problem at all, because this is true for the numerical sets we are interested in, that are \mathbb{N}, \mathbb{Z} and \mathbb{R}.

Property N.15: Third equivalent form for summations where the product of indexes divides a constant

Let n be a positive integer. Let g and h be any two functions defined on \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{d \mid n} \sum_{d^{\prime} \mid d} g(d^{\prime}) h\left(\frac{d}{d^{\prime}}\right) = \sum_{ab \mid n} g(a) h(b)
\prod_{d \mid n} \prod_{d^{\prime} \mid d} g(d^{\prime}) h\left(\frac{d}{d^{\prime}}\right) = \prod_{ab \mid n} g(a) h(b)

(*) The same observations made about Property N.14 are also valid now

Property N.16: Simplification, by means of the Möbius function, of a double summation extended to the divisors of a positive integer, and to the divisors of the divisors

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{ab \mid n} \mu(a) f(b) = f(n)

(*) The same observations made about Property N.13 are also valid now

Property N.17: Expression of logarithm as a summation of \Lambda

Let n be a positive integer. Then:

\sum_{d \mid n} \Lambda(d) = \log n
Property N.18: Möbius inversion formula

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} (the codomain does not matter(*)), and let g be the function defined for all n \in \mathbb{N}^{\star} as follows:

g(n) := \sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right)

Then

\sum_{d \mid n} g(d) = f(n)

for all n \in \mathbb{N}^{\star}.

(*) The same observations made about Property N.13 are also valid now

Lemma N.9: First lemma about summations with the Möbius function and the logarithm
\sum_{n \leq x} \sum_{d \mid n} \mu(d) \log \left(\frac{x}{d}\right) = O(x)

where the function on the left is defined for x \in \mathbb{N}^{\star}.

Lemma N.10: Second lemma about summations with the Möbius function and the logarithm
\sum_{n \leq x} \sum_{d \mid n} \mu(d) \log^2 \left(\frac{x}{d}\right) = 2x \log x + O(x)

where the function on the left is defined for x \in \mathbb{N}^{\star}.

Property N.19: Simplification of the double summation for n \leq x and for d \mid n

Let x be a positive integer. Let f be any function defined on positive integer numbers (the codomain does not matter(*)). Then:

\sum_{n \leq x} \sum_{d \mid n} f(d) = \sum_{n \leq x} \left \lfloor \frac{x}{n} \right \rfloor f(n)

(*) To be precise, it’s necessary that the sum operation is defined on the codomain, and it must be commutative. However in this context there is no problem at all, because this is true for the numerical sets we are interested in (\mathbb{N}, \mathbb{Z} and \mathbb{R}).

Property N.20: Second equivalent form for summations where the product of indexes is less than or equal to a constant

Let x be a positive integer number. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{n \leq x} \sum_{m \leq \left\lfloor \frac{x}{n} \right\rfloor} f(n, m) = \sum_{nm \leq x} f(n, m)

(*) The same observations made about Property N.14 are also valid now

Lemma N.11: Third lemma about summations with the Möbius function and the logarithm

Let x be a positive integer. Then:

\sum_{nm \leq x} \Lambda(n) \Lambda(m) - \sum_{n \leq x} \Lambda(n) \log n = \sum_{n \leq x} \sum_{d \mid n} \mu(d) \log^2 d
Lemma N.12: Preliminary Lemma for Selberg’s Theorem

Let x be a positive integer. Then:

\sum_{nm \leq x} \Lambda(n) \Lambda(m) + \sum_{n \leq x} \Lambda(n) \log n = \sum_{n \leq x} \sum_{d \mid n} \mu(d) \log^2 \left( \frac{n}{d} \right)
Lemma N.13: Preliminary Lemma for Selberg’s Theorem: asymptotic estimate

Let x be a positive integer. Then:

\sum_{nm \leq x} \Lambda(n) \Lambda(m) + \sum_{n \leq x} \Lambda(n) \log n = 2x \log x + O(x)
Proposition N.8: Consequence of Selberg’s Theorem
R(x) \log^2 x = O(x \log x) + \sum_{n \leq x} \left( \sum_{km = n} \Lambda(k) \Lambda(m) - \Lambda(n) \log n \right) R\left(\frac{x}{n} \right)
Corollary 1 of Proposition N.8: Consequence of Selberg’s Theorem
|R(x)| \log^2 x \leq \sum_{n \leq x} \left(\sum_{km = n} \Lambda(k) \Lambda(m) + \Lambda(n) \log n\right) \left|R\left(\frac{x}{n}\right)\right| + O(x)
Corollary 2 of Proposition N.8: Consequence of Selberg’s Theorem, second form

For every positive integer x, there are some real numbers a_1, \ldots, a_x such that \sum_{n \leq x} a_n = 2x \log x + O(x) and

|R(x)| \log^2 x \leq \sum_{n \leq x} a_n \left|R\left(\frac{x}{n}\right)\right| + O(x)
Property N.21: Equivalent form for summations where the product of indexes is less than or equal to a constant

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{ab \leq n} f(a, b) = \sum_{k \leq n} \sum_{ab = k} f(a, b)

(*) The same observations made about Property N.14 are also valid now

Property N.22: First equivalent form for summations where the product of indexes divides a constant

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{ad \mid n} f(a, d) = \sum_{ab = n} \sum_{d \mid b} f(a, d)

(*) The same observations made about Property N.14 are also valid now

Property N.23: Second equivalent form for summations where the product of indexes divides a constant

Let n be a positive integer. Let f be any function defined on \mathbb{N}^{\star} \times \mathbb{N}^{\star} (the codomain does not matter(*)). Then:

\sum_{ad \mid n} f(a, d) = \sum_{d \mid n} \sum_{a \mid \frac{n}{d}} f(a, d)

(*) The same observations made about Property N.14 are also valid now

Proposition N.12: Consequence of Selberg’s Theorem, integral form
|R(x)| \log^2 x \leq 2 \int_1^x \log t \left| R\left(\frac{x}{t}\right) \right| dt + O(x \log x)
Property N.24: Relationship between \alpha and \alpha^{\prime}, and between \beta and \beta^{\prime}

With reference to Definition N.23 (Constants \alpha^{\prime} and \beta^{\prime}):

\alpha \leq \alpha^{\prime}
\beta \leq \beta^{\prime}
Proposition N.23: Relationship between \alpha and \beta^{\prime}

With reference to Definitions N.23 and N.14:

\alpha \leq \beta^{\prime}