Don't take life too seriously: it's just a temporary situation

E’ la funzione “massimo comun divisore”, definita come il massimo intero che divida due (o più) interi maggiori di zero.

 

Se gli interi an hanno scomposizione in fattori primi Scomposizione in fattori primi di a(n), allora Formula per il calcolo del massimo comun divisore, ovvero il massimo comun divisore è il prodotto dei fattori primi, presi col minimo esponente che hanno tra le varie scomposizioni.

Se la scomposizione di due numeri non è nota, la funzione può essere calcolata velocemente con l’algoritmo di Euclide o con la sua variante binaria (v. costante di Porter).

 

Se il massimo comun divisore di due interi è 1, si dice che gli interi sono primi tra loro.

 

Definendo MCD(1, x) = 0 se x è irrazionale, si ottiene una funzione uguale alla funzione caratteristica dei numeri razionali, che è continua per x irrazionale, discontinua per x razionale e ha integrale di Riemann nullo su qualsiasi intervallo.

 

La funzione è commutativa, distributiva e associativa, ovvero:

MCD(a, b) = MCD(b, a);

MCD(na, nb) = nMCD(a, b);

MCD(a, b, c) = MCD(a, MCD(b, c)) = MCD(MCD(a, b), c).

 

Valgono inoltre le relazioni:

MCD(1, n) = MCD(n, 1) = 1;

MCD(n, n) = n;

Formula per il calcolo del massimo comun divisore;

mcm(a, MCD(a, b)) = a;

MCD(2p – 1, 2q – 1) = 2MCD(p, q) – 1.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.