Numeri primi – #1

I Matematici hanno provato fino ad oggi, in vano, di scoprire un qualche ordine nella sequenza dei numeri primi, e ho ragione di credere che questo è un mistero in cui la mente umana non potrà mai penetrare.

Leonhard Euler (1707-1783) 

Per oscuri motivi universitari, o forse non poi così oscuri, mi sono messo a cercare tra i risultati di Teoria dei Numeri sui primi e visto che ho messo da parte qualcosa di interessante, almeno secondo il mio standard, ho deciso di proporveli, a rate chiaramente.

Iniziamo con il ricordare la definizione di numero primo:
Def. 1 Un intero n \in \NN è detto primo se n > 1 e se gli unici divisori positivi di n sono 1 ed n stesso. Altrimenti il numero è detto composito.

La prima questione da investigare è: ma quanti sono in realtà i numeri primi? Finiti? Infiniti? 42? Prima di poter rispondere, a fondo, a questa domanda, come si fa quasi sempre in matematica, abbiamo bisogno di introdurre un paio di risultati preliminari che ci aiuteranno a risolvere.

Lemma 1. (La serie armonica) La serie \sum_{i=1}^{+\infty}\frac{1}{n} è divergente.

Dim. È sufficiente osservare la seguente relazione per le somme parziali:

    \begin{equation*} \begin{split} S_N = & \sum_{i=1}^{N}\frac{1}{n} = \sum_{i=1}^{N}\int_{n}^{n+1}\frac{1}{n}dx > \\      >& \sum_{i=1}^{N}\int_{n}^{n+1}\frac{1}{x}dx = \int_{1}^{N+1}\frac{1}{x}dx = \log(N+1) \end{split} \end{equation*}

e quindi S_N > \log(N+1) \rightarrow +\infty, ovvero la serie diverge.

Q.E.D.

Osserviamo che, inoltre, questo ci dice che la serie armonica diverge almeno in modo logaritmico. In qualche puntata successiva si potrebbe far vedere che in realtà diverge proprio in modo logaritmico.

Diamo adesso il seguente risultato sui numeri naturali:
Lemma 2. Ogni numero intero n > 1 è un numero primo oppure il prodotto di numeri primi.

Dim. Dimostriamolo per induzione su n. Il teorema è banalmente valido per n=2, supponiamolo vero per tutti gli interi <n e dimostriamolo per n. Se n è primo abbiamo finito, altrimenti n ha un divisore proprio d con d\neq 1, quindi n = dc con d<n e c<n, inoltre sia c > 1 sia d > 1, dunque possiamo applicare l’ipotesi induttiva e concludere.

Q.E.D.

Dati questi due ingredienti possiamo finalmente proporre un po’ di dimostrazioni del seguente teorema:

Teorema 1. I numeri primi sono infiniti.

Dimostrazione 0. [Euclide] Supponiamo per assurdo che i numeri primi siano finiti e siano rappresentanti dalla lista \{p_1,p_2,\ldots,p_n\}, consideriamo allora il numero M = p_1\cdot p_2 \cdot\ldots\cdot p_n, chiaramente questo numero è divisibile per ognuno dei p_i. Consideriamo invece il numero N = M + 1, questo non può essere divisibile per nessuno dei \{p_1,p_2,\ldots,p_n\}, ma questa era una lista esaustiva dei primi. Abbiamo raggiunto l’assurdo e l’assurdo deriva dall’aver supposto finiti i numeri primi.

Q.E.D.

Dimostrazione 1. [Euler]  Supponiamo per assurdo che i numeri primi siano finiti e siano rappresentanti dalla lista \{p_1,p_2,\ldots,p_n\}. A questo punto consideriamo la serie armonica:

(1)   \begin{equation*} \begin{split} \sum_{n=1}^{+\infty}\frac{1}{n} = & 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \cdots = \\ = & \left(1 + \frac{1}{p_1} + \frac{1}{p_1^2} + \frac{1}{p_1^3} + \cdots + \frac{1}{p_1^n} + \cdots \right)\cdot \\ & \left(1 + \frac{1}{p_2} + \frac{1}{p_2^2} + \frac{1}{p_2^3} + \cdots + \frac{1}{p_2^n} + \cdots \right)\cdot \\ & \vdots \\ & \left(1 + \frac{1}{p_n} + \frac{1}{p_n^2} + \frac{1}{p_n^3} + \cdots + \frac{1}{p_n^n} + \cdots \right) \end{split} \end{equation*}

abbiamo scritto la serie armonica come il prodotto delle serie geometriche di ragione 1/p_i \forall i=1,\ldots ,n poiché ogni elemento della serie armonica è il reciproco di un naturale e, per il lemma 2, ogni naturale è il prodotto di numeri primi. Dunque svolgendo tutti i prodotti dal secondo lato dell’uguaglianza otteniamo tutti gli elementi della serie armonica. A questo punto è sufficiente osservare che tutte le serie geometriche a secondo membro sono convergenti, dalla nota formula abbiamo che:

(2)   \begin{equation*} \sum_{n=1}^{+\infty}\frac{1}{n} = \frac{1}{1 - \frac{1}{p_1}} \cdot \frac{1}{1 - \frac{1}{p_2}} \cdot \cdots \cdot \frac{1}{1 - \frac{1}{p_n}} \end{equation*}

ma questo è assurdo, infatti dal lemma 1 abbiamo che la serie armonica è divergente, mentre dall’equazione 2 abbiamo che è uguale ad un prodotto finito. L’assurdo deriva dall’aver supposto finiti i numeri primi.

Q.E.D.

Un’altra, elegante, dimostrazione di questo fatto è quella data da Erdös. Introduciamo prima la seguente funzione:
Def 2. Funzione di distribuzione dei numeri primi:

(3)   \begin{equation*} \pi(x) = \{\text{numero dei numeri primi } < x \} \end{equation*}

Possiamo dunque dare la prova:

Dimostrazione 2. [Erdös]  Osserviamo, da principio, che ogni numero intero n \in \NN può essere rappresentanto nella forma n = rs^2 con r \in N privo di quadrati ed s intero qualsiasi. Ad esempio basta considerare s il più grande intero tale s^2 | n e porre r = n/s^2. Chiaramente questa rappresentazione non è unica, per ottenere una sovrastima del numero di partizioni di questo tipo abbiamo, in primo luogo, bisogno di sapere quanti sono i numeri r < n privi di quadrati. Ognuno di questi corrisponde ad una serie di primi distinti il cui prodotto è < n e di questi primi una soprastima è data da \pi(n), dunque ci sono al più 2^{\pi(n)} numeri privi di quadrati \leq n. La seconda domanda a cui dobbiamo rispondere per ottenere la stima è più semplice, infatti il numero interi s il cui quadrato è minore di n è semplicemente \sqrt{n}. Riassumendo se fattorizziamo ogni numero \leq n nella forma rs^2 abbiamo al più 2^{\pi(n)} possibilità per r e \sqrt{n} possibilità per s, ovvero abbiamo ottenuto che:

(4)   \begin{equation*} 2^{\pi(n)}\sqrt{n} \geq n \end{equation*}

dividendo per \sqrt{n} ambo i membri ed estraendone i logaritmi in base 2:

(5)   \begin{equation*} \pi(n) \geq \frac{\log n}{2} \end{equation*}

dunque \pi(n) \rightarrow +\infty per n\rightarrow \infty, ovvero i numeri primi sono infiniti.

Q.E.D.

Si osservi che questa dimostrazione ci ha fornito anche una stima sulla distribuzione dei numeri primi data dall’eq. 5, a questo punto conviene farne un disegnino tanto per capire ad occhio come è la stima:

[singlepic id=454 w=430 h=326 float=center]

si può fare di meglio, molto di meglio in effetti.

A questo punto direi che per il #1 basta e avanza. Al prossimo giro con un altro paio di dimostrazioni del Teorema 1. e qualche altra cosuccia.

Bibliografia.

  1. Euclide, Elementi, Proposizione IX.20
  2. Apostol, T.M., Introduction to Analytic Number Theory, Springer, 1976.
  3. P. Erdös, “Uber die Reihe \sum \frac{1}{p}“, Mathematica, Zutphen B 7 (1938).

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.