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)
Proposition N.7A: The functions W and V are limited The functions W and V are limited.
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.

Corollary I of Proposition N.7A: \alpha and \beta are real The constants \alpha and \beta defined by Definition N.14 are real numbers.
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}
Corollary II of Proposition N.7A: \alpha^{\prime} and \beta^{\prime} are real The constants \alpha^{\prime} and \beta^{\prime} defined by Definition N.23 are real numbers.
Proposition N.23: Relationship between \alpha and \beta^{\prime}

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

\alpha \leq \beta^{\prime}
Proposition N.24: Overestimation of the absolute value of the integral of V between 0 and a positive number

There exists a real number A \gt 0 such that, for all \xi \gt 0:

\left| \int_0^{\log \xi} V(u)\ du \right| \lt A
Corollary of Proposition N.24: Overestimation of the absolute value of the integral of V between two positive or null values

There exists a real number A \gt 0 such that, for all a \geq 0 and for all b \gt a:

\left| \int_{a}^{b} V(u)\ du \right| \lt 2A
Lemma N.14: Overestimation of the integral of V in the intervals in which it doesn’t change sign

Let [a, b] be an interval in which the function V is always positive or always negative. Then there exists a positive constant A such that:

\int_{a}^{b} |V(u)|\ du \lt 2A
Proposition N.25: Overestimation of the absolute value of V after one zero of it

Let t be a zero of V. Then, for all h \geq 0:

|V(t + h)| \leq 1 - \frac{1}{e^h} + O\left(\frac{1}{t}\right)
Proposition N.26: Relationship between \alpha^{\prime} and \beta^{\prime}

With reference to Definition N.23:

\alpha^{\prime} \leq \beta^{\prime}
Lemma N.15: Overestimation of the integral of |V| better than the one by limit superior, first case

Suppose that \alpha^{\prime} \gt 0. Let \delta and a be such that \delta \geq \alpha^{\prime} and a \geq 0. If in the interval [a, a + \delta - \alpha^{\prime}] the function |V| has at least one zero, and if there is a constant h \lt 1 such that:

(\delta - \alpha^{\prime}) \alpha^{\prime} + \frac{(\alpha^{\prime})^2}{2} = \delta h \alpha^{\prime}

then:

\int_a^{a+\delta} |V(u)|\ du \leq \delta h \alpha^{\prime} + o(1)
Lemma N.16: In an interval, if V has no zeroes it changes sign at most once

Let I be a real interval in which V has no zeroes. Then V changes sign at most once in I.

Lemma N.17: Overestimation of the integral of |V| better than the one by limit superior, second case

Suppose that \alpha^{\prime} \gt 0. Let A be the constant of Lemma N.14, let \delta \geq \alpha^{\prime} and a \geq 0. If in the interval [a, a + \delta - \alpha^{\prime}] the function |V| has no zeroes, and if there is a constant k \lt 1 such that

4A + (\alpha^{\prime})^2 = \delta k \alpha^{\prime}

then:

\int_a^{a+\delta} |V(u)|\ du \leq \delta k \alpha^{\prime} + o(1)
Proposition N.27: Overestimation of the integral of |V| better than the one by limit superior, in intervals of appropriate length

Suppose that \alpha^{\prime} \gt 0. Let \delta \geq \frac{4A}{\alpha^{\prime}} + \frac{3 \alpha^{\prime}}{2}, where A is the constant of Lemma N.14. Then there exists a constant h \lt 1 such that, for all a \geq 0:

\int_a^{a+\delta} |V(u)|\ du \leq \delta h \alpha^{\prime} + o(1)
Property N.25: Calculating the values of a multiplicative function

Let f: \mathbb{N}^{\star} \rightarrow \mathbb{R} be a multiplicative function and let n be a positive integer. Let n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k} be the factorization of n (with p_1, \ldots, p_k distinct prime factors and a_1, \ldots, a_k positive integers). Then:

f(n) = f\left(p_1^{a_1}\right) \cdot \ldots \cdot f\left(p_k^{a_k}\right)
Property N.26: Calculating the values of a completely multiplicative function

Let f: \mathbb{N}^{\star} \rightarrow \mathbb{R} be a completely multiplicative function and let n be a positive integer. Let n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k} be the factorization of n (with p_1, \ldots, p_k distinct prime factors and a_1, \ldots, a_k positive integers). Then:

f(n) = \left(f(p_1)\right)^{a_1} \cdot \ldots \cdot \left(f(p_k)\right)^{a_k}
Proposition N.28: Dual Möbius inversion formula

Let n be a positive natural number and let f be a function defined on the divisors of n.
Let g be the following function defined on the divisors of n:

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

Then, for every k \mid n:

f(k) = \sum_{k \mid d \mid n} \mu \left(\frac{d}{k}\right) g(d)
Proposition N.29: Number of integers pairs having a fixed square-free least common multiple

Let d be a square-free positive integer. The number of ordered pairs of positive integers having least common multiple d is equal to:

3^{\omega(d)}
Proposition N.30: Asymptotic order of the sum of d(n) for the first positive integers

Let x be a positive integer. Then:

\sum_{n \leq x} d(n) = x \log x + O(x)
Proposition N.31: Asymptotic order of the sum of d(n) over n for the first positive integers

Let x be a positive integer. Then:

\sum_{n \leq x} \frac{d(n)}{n} \gg \log^2 x