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.
Proprietà N.1A: Nei numeri naturali, un divisore è minore o uguale di un dividendo positivo Siano a e b due numeri naturali, con a \gt 0. Se b \mid a, allora b \leq a.
Proprietà N.1B: Numero primo, proprietà caratteristica o definizione alternativa Un numero primo è un numero intero p > 1 tale che, se p \mid bc, allora p \mid b oppure p \mid c, per qualunque coppia di interi b e c. In altri termini, p non può dividere un prodotto di interi bc senza dividere almeno uno dei due 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 reali non negativi, 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 reali non negativi, 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)
Lemma N.6A: Funzione somma dei logaritmi di una frazione al variare del denominatore, forma generalizzata

Sia h \in \mathbb{R}, h \gt 0. Allora:

\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)}
Corollario della Proposizione N.7: Ordine di grandezza della funzione simil-fattoriale basata su \Lambda^{\star} \sum_{r = 1}^x \frac{\Lambda(r)}{r} = \log x + O(1)
Teorema N.7: Limite inferiore e limite superiore della funzione \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}
Corollario del Teorema N.7: Limite inferiore e limite superiore della funzione \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}
Corollario II del Teorema N.7: Teorema di Chebyshev, versione forte Se la funzione \pi(x) / \frac{x}{\log x} tende a un limite, questo limite è 1.
Teorema N.8: Teorema dei numeri primi \pi(x) \sim \frac{x}{\log x}
Teorema N.9: Teorema dei numeri primi, versione forte \pi(x) \sim \mathrm{Li}(x)
Lemma N.7: Condizione sufficiente per la validità del Teorema dei Numeri Primi Una condizione sufficiente per la validità del Teorema dei Numeri Primi è la seguente:

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

dove la funzione V è definita nella Definizione N.13.

Lemma N.8 Fissato un numero intero x \gt 0, le seguenti disuguaglianze sono equivalenti:

  • |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
Teorema N.10: Teorema di Selberg
R(x) \log x + \sum_{n = 1}^x \Lambda(n) R\left(\frac{x}{n}\right) = O(x)
Proprietà N.7: Caratterizzazione dei numeri interi privi di quadrati Un numero intero è privo di quadrati se e solo se nella sua fattorizzazione compaiono solo fattori primi distinti.
Proprietà N.8: Una proprietà del conteggio dei divisori di un numero intero maggiore di 1 Sia n \gt 1 un numero intero. Siano P_n e D_n i seguenti insiemi:

P_n := \left\{ \begin{gathered} \text{divisori di $n$ privi di quadrati,} \\ \text{che sono il prodotto di un numero pari di fattori primi} \end{gathered}\right\}
D_n := \left\{ \begin{gathered} \text{divisori di $n$ privi di quadrati,} \\ \text{che sono il prodotto di un numero dispari di fattori primi} \end{gathered}\right\}

Allora |P_n| = |D_n|.

Proprietà N.9: Una proprietà del prodotto dei divisori di un numero intero positivo avente almeno due fattori primi distinti Sia n un numero intero positivo avente almeno due fattori primi distinti. Siano P_n e D_n gli insiemi definiti nella Proprietà N.8. Allora \prod_{a \in P_n} a = \prod_{b \in D_n} b.
Proprietà N.9 (seconda forma): Una proprietà del prodotto dei divisori di un numero intero positivo avente almeno due fattori primi distinti

Sia n un numero intero positivo avente almeno due fattori primi distinti. Allora:

\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
Proprietà N.8 (seconda forma): Una proprietà del conteggio dei divisori di un numero intero maggiore di 1

Sia n \gt 1 un numero intero. Allora:

\sum_{d \mid n} \mu(d) = 0
Proprietà N.10: Una proprietà del prodotto dei divisori di un numero intero positivo

Sia n \in \mathbb{N}^{\star}. Allora:

\prod_{d \mid n} d^{\mu(d)} = \frac{1}{\Lambda^{\star}(n)}
Proprietà N.10 (forma logaritmica): Una proprietà del prodotto dei divisori di un numero intero positivo

Sia n \in \mathbb{N}^{\star}. Allora:

\sum_{d \mid n} \mu(d) \log d = - \Lambda(n)
Proprietà N.11: Una proprietà del conteggio dei divisori di un numero intero positivo

Sia n \in \mathbb{N}^{\star}. Allora:

\sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{se $n = 1$} \\ 0 & \text{altrimenti} \end{cases}
Proprietà N.12: Espressione di \Lambda^{\star} mediante \mu

Sia n \in \mathbb{N}^{\star}. Allora:

\prod_{d \mid n} \left( \frac{n}{d} \right)^{\mu(d)} = \Lambda^{\star}(n)
Proprietà N.12 (forma logaritmica): Espressione di \Lambda mediante \mu

Sia n \in \mathbb{N}^{\star}. Allora:

\sum_{d \mid n} \mu(d) \log \frac{n}{d} = \Lambda(n)
Proprietà N.13: Scambio di d ed \frac{n}{d} nelle sommatorie estese ai divisori di un numero intero positivo

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} \times \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

\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)

(*) Per la precisione, è necessario che sull’insieme di arrivo siano definite l’operazione di somma e di prodotto, e che esse siano commutative. Tuttavia in questo contesto è inutile porsi il problema, perché ciò è vero per gli insiemi numerici che ci interessano (\mathbb{N}, \mathbb{Z} ed \mathbb{R}).

Proprietà N.14: Forma equivalente per le sommatorie in cui compaiono d ed \frac{n}{d}

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} \times \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

\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)

(*) Per la precisione, è necessario che sull’insieme di arrivo siano definite l’operazione di somma e di prodotto, e che esse siano commutative. Tuttavia in questo contesto è inutile porsi il problema, perché ciò è vero per gli insiemi numerici che ci interessano (\mathbb{N}, \mathbb{Z} ed \mathbb{R}).

Proprietà N.15: Terza forma equivalente per le sommatorie dove il prodotto degli indici divide una costante

Sia n un numero intero positivo. Siano g ed h due qualunque funzioni definite su \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

\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)

(*) Valgono le stesse considerazioni fatte per la Proprietà N.14

Proprietà N.16: Semplificazione mediante la funzione di Möbius di una doppia sommatoria estesa ai divisori di un numero intero positivo, e ai divisori dei divisori

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

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

(*) Valgono le stesse considerazioni fatte per la Proprietà N.13

Proprietà N.17: Espressione del logaritmo come sommatoria di \Lambda

Sia n un numero intero positivo. Allora:

\sum_{d \mid n} \Lambda(d) = \log n
Proprietà N.18: Formula di inversione di Möbius

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)), e sia g la funzione definita per ogni n \in \mathbb{N}^{\star} come segue:

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

Allora

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

per ogni n \in \mathbb{N}^{\star}.

(*) Valgono le stesse considerazioni fatte per la Proprietà N.13.

Lemma N.9: Primo lemma sulle sommatorie con la funzione di Möbius e il logaritmo
\sum_{n \leq x} \sum_{d \mid n} \mu(d) \log \left(\frac{x}{d}\right) = O(x)

dove la funzione sulla sinistra si intende definita per x \in \mathbb{N}^{\star}.

Lemma N.10: Secondo lemma sulle sommatorie con la funzione di Möbius e il logaritmo
\sum_{n \leq x} \sum_{d \mid n} \mu(d) \log^2 \left(\frac{x}{d}\right) = 2x \log x + O(x)

dove la funzione sulla sinistra si intende definita per x \in \mathbb{N}^{\star}.

Proprietà N.19: Semplificazione della doppia sommatoria per n \leq x e per d \mid n

Sia x un intero positivo. Sia f una qualunque funzione definita sui numeri interi positivi (non importa l’insieme di arrivo(*)). Allora:

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

(*) Per la precisione, è necessario che sull’insieme di arrivo sia definita l’operazione di somma, e che essa sia commutativa. Tuttavia in questo contesto è inutile porsi il problema, perché ciò è vero per gli insiemi numerici che ci interessano (\mathbb{N}, \mathbb{Z} ed \mathbb{R}).

Proprietà N.20: Seconda forma equivalente per le sommatorie dove il prodotto degli indici è minore o uguale di una costante

Sia x un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} \times \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

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

(*) Valgono le stesse considerazioni fatte per la Proprietà N.14

Lemma N.11: Terzo lemma sulle sommatorie con la funzione di Möbius e il logaritmo

Sia x un numero intero positivo. Allora:

\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: Lemma alla base del Teorema di Selberg

Sia x un numero intero positivo. Allora:

\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: Lemma alla base del Teorema di Selberg: stima asintotica

Sia x un numero intero positivo. Allora:

\sum_{nm \leq x} \Lambda(n) \Lambda(m) + \sum_{n \leq x} \Lambda(n) \log n = 2x \log x + O(x)
Proposizione N.8: Conseguenza del Teorema di Selberg
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)
Corollario 1 della Proposizione N.8: Conseguenza del Teorema di Selberg
|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)
Corollario 2 della Proposizione N.8: Conseguenza del Teorema di Selberg, seconda forma

Per ogni intero positivo x, esistono dei numeri reali a_1, \ldots, a_x tali che \sum_{n \leq x} a_n = 2x \log x + O(x) e

|R(x)| \log^2 x \leq \sum_{n \leq x} a_n \left|R\left(\frac{x}{n}\right)\right| + O(x)
Proprietà N.21: Forma equivalente per le sommatorie dove il prodotto degli indici è minore o uguale di una costante

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} \times \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

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

(*) Valgono le stesse considerazioni fatte per la Proprietà N.14

Proprietà N.22: Prima forma equivalente per le sommatorie dove il prodotto degli indici divide una costante

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} \times \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

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

(*) Valgono le stesse considerazioni fatte per la Proprietà N.14

Proprietà N.23: Seconda forma equivalente per le sommatorie dove il prodotto degli indici divide una costante

Sia n un numero intero positivo. Sia f una qualunque funzione definita su \mathbb{N}^{\star} \times \mathbb{N}^{\star} (non importa l’insieme di arrivo(*)). Allora:

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

(*) Valgono le stesse considerazioni fatte per la Proprietà N.14

Proposizione N.12: Conseguenza del Teorema di Selberg, forma integrale
|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)