Calcolo della probabilità
di un MCD dato

Costruiamo un programma che conti le coppie (i,j) di interi positivi <= n tali che MCD(i,j)=1, MCD(i,j)=2, ..., MCD(i,j)=d (con d<=n).
Il risultato è una lista c di lunghezza di d. Per accelerare il conto delle coppie per cui MCD(i,j)=d, contiamo solo le coppie (i,j) con i<j. Quindi moltiplichiamo per 2 e aggiungiamo 1 (per contare le coppie (i,j) con i>j, e la singola coppia (d,d)).

Ecco il conto delle coppie di interi tra 1 e n=200, con MCD di valore i=1 oppure 2 ... oppure 5.

Questa formula prevede una probabilità di che il MCD tra due numeri sia i=1, una probabilità di che il MCD tra due numeri sia i=2, una probabilità di che il MCD tra due numeri sia i=3, e così via.

Scriviamo i risulati ottenuti e quelli previsti sotto forma di tabella.

La differenza tra il numero di coppie previsto:

                 , , , ...
                 
(con n=200) e quello ottenuto è difficilmente visibile a occhio nudo.

Controlliamo che la somma delle probabilità previste per i possibili valori di MD(n,m) faccia uno:

Solo per curiosità, aggiungiamo un grafico a densità dei valori di MCD(n,m), e del sottoinsieme degli (n,m) con MCD(n,m)=1 (delle coppie (n,m) di coprimi). La distribuzione appare intricata e priva di regolarità evidenti; tanto più ci sorprende il fatto che la percentaule delle con MCD(n,m) sia esprimibile con una formula così semplice,