Coπrimalità

Presi due numeri naturali maggiori di $1$, qual è la probabilità che essi siano coprimi, ovvero che il loro massimo comun divisore sia $1$?

La risposta è sorprendente: la probabilità è $p=\dfrac{1}{\zeta(2)}=\dfrac{6}{\pi^2}\simeq 60{,}8\%\ $ ($\zeta$ è la funzione zeta di Riemann), la dimostrazione è data in calce al post.

Ho provato a “verificare sul campo” questo valore, considerando $n$ numeri da $2$ a $n+1$ e contando quante sono le coppie ordinate $(a,b)$ di numeri coprimi, con $2\leq a,b \leq n+1$. Chiamo $c(n)$ il numero di queste coppie. Il rapporto $c(n)/n^2$ dovrebbe convergere a $\dfrac{6}{\pi^2}$ al tendere di $n$ a infinito. Le immagini qui sotto testimoniano che questo in effetti accade. Nel secondo grafico, quello con scala delle ascisse logaritmica, nelle ordinate ho preso la radice cubica per non far appiattire in modo illeggibile il grafico. Tenete quindi presente che, ad esempio, a $0{,}05$ corrisponde un valore di $0{,}000125$. Per $n=65536$ il rapporto fra $c(n)/n^2$ e $6/π^2$ differisce da $1$ per circa $10^{-6}\ $.

Così però ho fatto un “esperimento”, ancorché esaustivo, con numeri “piccoli”, minori o uguali a $65537$. Ho allora fatto anche tre test Montecarlo, nel primo prendendo per $2^{10}=1024$ volte $2^{20}=1048576$ coppie di numeri generati casualmente, compresi fra $2$ e $2^{96}+1\simeq79\times10^{27}$ e ho calcolato il rapporto $r$ fra coppie di numeri coprimi e numero totale di coppie. Il risultato, riportato in termini di media e deviazione standard è stato

$r=(0{,}999974\pm0{,}000784)\cdot 6/\pi^2$ dove l’errore atteso sulla media è dell’ordine di $0{,}000025$ e la deviazione standard attesa è $0{,}000760$. Nell’immagine qui sotto la distribuzione dei dati confrontata a quella teorica. Nelle ascisse è riportato il valore $\dfrac{r}{6/\pi^2}$.

Nel secondo test Montecarlo, ho preso $2^{14}=16384$ volte $2^{16}=65536$ coppie di numeri generati casualmente, sempre compresi fra $2$ e $2^{96}+1$ e, come prima, ho calcolato il rapporto $r$ fra coppie di numeri coprimi e numero totale di coppie. Il risultato, riportato in termini di media e deviazione standard è stato $r=(1{,}000028\pm0{,}003143)\cdot 6/\pi^2$ dove l’errore atteso sulla media è dell’ordine di $0{,}000025$ e la deviazione standard attesa è $0{,}003137$. Nell’immagine qui sotto la distribuzione dei dati confrontati a quella teorica. Nelle ascisse, come prima, è riportato il valore $\dfrac{r}{6/\pi^2}$.

Nel terzo test Montecarlo, ho preso $2^{16}=65536$ volte $2^{14}=16378$ coppie di numeri generati casualmente, sempre compresi fra $2$ e $2^{96}+1$ e, come prima, ho calcolato il rapporto $r$ fra coppie di numeri coprimi e numero totale di coppie. Il risultato, riportato in termini di media e deviazione standard è stato $r=(1{,}000010\pm0{,}006261)\cdot 6/\pi^2$ dove l’errore atteso sulla media è dell’ordine di $0{,}000025$ e la deviazione standard attesa è $0{,}006274$. Nell’immagine qui sotto la distribuzione dei dati confrontati a quella teorica. Nelle ascisse, come prima, è riportato il valore $\dfrac{r}{6/\pi^2}$. Come si vede, maggiore è il numero di dati, maggiore è l’aderenza del grafico delle frequenze a quello della gaussiana.

In conclusione, direi che c’è un buon accordo fra teoria e “risultati sperimentali”.

Dimostrazione della probabilità di coprimalità

Preso un numero naturale maggiore di $2$, qual è la probabilità che sia divisibile per $2$, ovvero che lo abbia fra i suoi fattori primi? È chiaramente $\dfrac{1}{2}$. E qual è la probabilità che sia divisibile per $3$, ovvero che lo abbia fra i suoi fattori primi? Analogamente è $\dfrac{1}{2}$. In generale, se $p_i$ è un numero primo, la probabilità che un numero lo abbia fra i suoi fattori primi è  $\dfrac{1}{p_i}$.

Se consideriamo due numeri naturali maggiori di $2$, qual è la probabilità che entrambi abbiano come fattore comune un numero primo $p_i$? È $\dfrac{1}{p_i}\cdot\dfrac{1}{p_i}=\dfrac{1}{p_i^2}$. La probabilità che essi non abbiano entrambi $p_i$ come fattore primo è quindi $1-\dfrac{1}{p_i^2}$.

La probabilità che due numeri naturali maggiori di $2$ non abbiano nessun fattore primo in comune sarà quindi $$p=\prod_{i=1}^\infty\left(1-\dfrac{1}{p_i^2} \right ) =\left(1-\dfrac{1}{2^2} \right )\left(1-\dfrac{1}{3^2} \right )\left(1-\dfrac{1}{5^2} \right )\ldots\ .$$ Ora consideriamo $\dfrac{1}{p}$, si avrà $$\dfrac{1}{p}=\prod_{i=1}^\infty\dfrac{1}{\left(1-\dfrac{1}{p_i^2} \right )} =\dfrac{1}{\left(1-\dfrac{1}{2^2} \right )}\cdot\dfrac{1}{\left(1-\dfrac{1}{3^2} \right )}\cdot\dfrac{1}{\left(1-\dfrac{1}{5^2} \right )}\cdot\ldots$$ Ora sviluppando in serie si avrà $$\dfrac{1}{p}=\left(1+\dfrac{1}{2^2}+\dfrac{1}{(2^2)^{ ^2}}+\ldots\right )\left(1+\dfrac{1}{3^2}+\dfrac{1}{(3^2)^{ ^2}}+\ldots\right )\left(1+\dfrac{1}{5^2}+\dfrac{1}{(5^2)^{ ^2}}+\ldots\right )\cdot\ldots=\\=1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\dfrac{1}{(2^2)^{ ^2}}+\dfrac{1}{5^2}+\dfrac{1}{2^2\cdot 3^2}+\dfrac{1}{7^2}+\dfrac{1}{(2^2)^{ ^3}} +\ldots = \sum_{n=1}^{\infty}\dfrac{1}{n^2} =\zeta(2)\ .$$ Questo perché i prodotti dei termini daranno tutti, e solo una volta, i reciproci dei quadrati dei numeri naturali diversi da $0$, per il teorema fondamentale dell’aritmetica. Si ha dunque, in definitiva, $$p=\dfrac{1}{\zeta(2)}=\dfrac{6}{\pi^2}\ .$$

La produttoria converge molto più rapidamente della sommatoria, come si può intuire dallo sviluppo in serie della produttoria stessa.