Enunciati di teoria dei numeri

Segue una lista degli enunciati presenti all’interno dei nostri articoli di teoria dei numeri.

Titolo e riferimento Enunciato
Teorema N.1: Teorema fondamentale dell’aritmetica (non dimostrato) Ogni numero intero maggiore di 1 si può scrivere come prodotto di numeri primi. Inoltre tale scrittura, chiamata fattorizzazione o scomposizione in fattori primi, è unica a meno dell’ordine dei fattori.
Teorema N.2: Infinità dei numeri primi I numeri primi sono infiniti.
Proprietà N.1: Maggiorazione dei binomiali Per ogni n > 0 e per ogni m: \binom{n}{m} \leq 2^{n-1}
Proprietà N.2: Minorazione dei binomiali centrali del Triangolo di Tartaglia Per ogni n \geq 2: \binom{n}{\frac{n}{2}} \geq \frac{2^n}{n} se n è pari, e \binom{n}{\left \lceil \frac{n}{2} \right \rceil} = \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor} \geq \frac{2^n}{n} se n è dispari.
Proprietà N.3: Minorazione del binomiale centrale del triangolo di Tartaglia, n pari Per ogni n \geq 2 pari: \binom{n}{\frac{n}{2}} \geq \sqrt{2^{n}}
Proposizione N.1: Maggiorazione del prodotto dei numeri primi fino ad x Per ogni x > 0: \theta^{\star}(x) = \prod_{1 \leq p \leq x} p \leq 2^{2(x-1)}
Teorema N.3: Postulato di Bertrand Per ogni n > 0, esiste un numero primo compreso tra n + 1 e 2n.
Lemma N.1: Fattorizzazione del binomiale \binom{2n}{n} Nella fattorizzazione del binomiale \binom{2n}{n}, per n > 0, un numero primo p non può avere un esponente maggiore di \log_p 2n.
Proposizione N.2: Calcolo di \psi^{\star}(x) Per ogni intero x > 0: \psi^{\star}(x) = \prod_{p \leq x} p^{\left \lfloor \log_p x \right \rfloor}
Corollario della Proposizione N.2: Maggiorazione di \psi^{\star}(x) mediante \pi(x) Per ogni intero x > 0: \psi^{\star}(x) \leq x^{\pi(x)}
Proposizione N.3: Minorazione di \psi^{\star}(x) Per ogni intero x > 0: \psi^{\star}(x) \geq \sqrt[3]{2^x}
Lemma N.2: Riformulazione di \psi^{\star}(x) (“calcolo per righe”) Per ogni intero 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)
Proposizione N.4: Collegamento tra le funzioni \psi^{\star} e \theta^{\star} Per ogni intero x > 0: \psi^{\star}(x) = \theta^{\star}(x) \cdot \theta^{\star}(\sqrt{x}) \cdot \dots \cdot \theta^{\star}(\sqrt[R]{x}), dove R := \left \lfloor \log_2 x \right \rfloor.
Lemma N.3: Minorazione di \theta^{\star}(x) mediante \pi(x) Per ogni numero reale \delta \geq 0 e per ogni x \gt 1: \theta^{\star}(x) \gt \left(x^{\delta}\right)^{\pi(x) - x^{\delta}}.
Teorema N.4: Equivalenza asintotica e ordine di grandezza di \theta(x) e \psi(x) Le funzioni \theta(x) e \psi(x) sono asintoticamente equivalenti ed hanno ordine x: \theta(x) \sim \psi(x), \theta(x) \asymp x \asymp \psi(x).
Teorema N.5: Equivalenza asintotica tra \pi(x) e \frac{\theta(x)}{\log x} \pi(x) \sim \frac{\theta(x)}{\log x}
Corollario del Teorema N.5: Equivalenza asintotica tra \pi(x) e \frac{\psi(x)}{\log x} \pi(x) \sim \frac{\psi(x)}{\log x}
Corollario II del Teorema N.5: Teorema di Chebyshev: ordine di grandezza di \pi(x) \pi(x) \asymp \frac{x}{\log x}
Corollario II del Teorema N.5: Teorema di Chebyshev: ordine di grandezza di \pi(x) \pi(x) \asymp \frac{x}{\log x}
Lemma N.4: Lemma dell’area dell’istogramma Siano c_1, c_2, \dots, c_n dei numeri naturali, con n > 0. Sia f: \{1, 2, ..., n\} \rightarrow \mathbb{R} una funzione. Allora l’area A dell’istogramma composto da n rettangoli, ciascuno avente base c_i ed altezza f(i), data da A = c_1 f(1) + c_2 f(2) + \ldots + c_n f(n) = \sum_{i=1}^{n} c_i f(i), si può calcolare anche con la 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} dove C_k := c_1 + c_2 + \ldots + c_k = \sum_{i=1}^{k} c_i.
Lemma N.5: Lemma dell’area dell’istogramma, seconda forma Siano c_1, c_2, \dots, c_n dei numeri naturali, con n > 0. Sia f: \{1, 2, ..., n\} \rightarrow \mathbb{R} una funzione, e sia \widetilde{f} una sua estensione di classe C^1. Allora l’area A dell’istogramma composto da n rettangoli, ciascuno avente base c_i ed altezza f(i), data da A = c_1 f(1) + c_2 f(2) + \ldots + c_n f(n) = \sum_{i=1}^{n} c_i f(i), si può calcolare anche con la formula C(n) f(n) - \int_1^n \overline{C}(k) \widetilde{f}'(t) dt dove C: \{1, 2, ..., n\} \rightarrow \mathbb{N} è la funzione definita da C(k) := c_1 + c_2 + \ldots + c_k = \sum_{i=1}^{k} c_i.
Teorema N.6: Approssimazione della somma degli inversi dei primi numeri interi Per ogni intero 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
dove la base del logaritmo è il numero di Nepero e, mentre \gamma \approx 0,58 è la costante di Eulero.
In particolare:
\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).
Proprietà N.4: Maggiorazioni e minorazioni del valore assunto da una funzione definita su numeri interi, per mezzo di integrali di un’estensione

Sia f: I \rightarrow \mathbb{R} una funzione definita su un insieme I \subset \mathbb{Z}.
Sia \overset{\sim}{f}: \overline{I} \rightarrow \mathbb{R} un’estensione di f, dove \overline{I} := \bigcup_{n \in I} [n, n + 1). Allora:

  • Se \overset{\sim}{f} è crescente, allora f(n) \leq \int_n^{n+1} \overset{\sim}{f}(t) dt
  • Se \overset{\sim}{f} è decrescente, allora f(n) \geq \int_n^{n+1} \overset{\sim}{f}(t) dt

Sia \underset{\sim}{f}: \underline{I} \rightarrow \mathbb{R} un’estensione di f, dove \underline{I} := \bigcup_{n \in I} (n - 1, n]. Allora:

  • Se \underset{\sim}{f} è crescente, allora \int_{n-1}^n \underset{\sim}{f}(t) dt \leq f(n)
  • Se \underset{\sim}{f} è decrescente, allora \int_{n-1}^n \underset{\sim}{f}(t) dt \geq f(n)
Lemma N.6: Funzione somma dei logaritmi di una frazione al variare del denominatore \sum_{n=1}^x \log \left(\frac{x}{n} \right) = O(x)
Proposizione N.5: Ordine di grandezza del fattoriale x! = x^x \cdot e^{O(x)}
Proprietà N.5: Numero di multipli di un dato numero, compresi tra 1 ed x

Siano n ed x due interi positivi. Il numero di multipli di n compresi nell’intervallo [1, x] è \left \lfloor \frac{x}{n} \right \rfloor.

Proposizione N.6: Il fattoriale e la funzione \Lambda^{\star} Per ogni intero x \gt 0: x! = \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\left \lfloor \frac{x}{r} \right \rfloor}
Proprietà N.6: Connessione tra \Lambda^{\star} e \psi^{\star} Per ogni intero x \gt 0: \prod_{r = 1}^x \Lambda^{\star}(r) = \psi^{\star}(x)
Proposizione N.7: Ordine di grandezza della funzione simil-fattoriale basata su \Lambda^{\star} \prod_{r = 1}^x \left( \Lambda^{\star}(r) \right)^{\frac{x}{r}} = x^x \cdot e^{O(x)}