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

 

La funzione può essere estesa agli interi negativi, prendendone il valore assoluto: MCD(m, n) = MCD(|m|, |n|).

La funzione può essere estesa ai numeri complessi con parti intere e immaginarie intere: MCD(a + ib, c + id) = MCD(a, c) + iMCD(b, d).

 

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

 

Alcune proprietà:

MCD(0, n) = MCD(n, 0) = n;

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

MCD(n, n) = n;

MCD(a, b) = MCD(a + b, b) = MCD(ab, b), per a > b;

MCD(n mod m, m) = MCD(n, m);

MCD(an, bn) = MCD(a, b)n;

MCD(a, b)MCD(c, d) = MCD(MCD(ac, ad), MCD(bc, bd));

Formula per il calcolo del massimo comun divisore;

mcm(m, n)MCD(m, n) = mn;

mcm(m, MCD(m, n)) = m;

MCD(m, mcm(m, n)) = m;

MCD(k, mcm(m, n)) = mcm(MCD(k, m), MCD(k, n));

mcm(k, MCD(m, n)) = MCD(mcm(k, m), mcm(k, n));

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

MCD(np – 1, nq – 1) = nMCD(p, q) – 1 (Knuth);

se p / MCD(p, q) e q / MCD(p, q) sono dispari, MCD(np + 1, nq + 1) = nMCD(p, q) + 1; altrimenti MCD(np + 1, nq + 1) = 1, se n è pari, e MCD(np + 1, nq + 1) = 2, se n è dispari (M. Fiorentini, 2018);

se q / MCD(p, q) è pari, MCD(np + 1, nq – 1) = nMCD(p, q) + 1; altrimenti MCD(np + 1, nq – 1) = 1, se n è pari, e MCD(np + 1, nq – 1) = 2, se n è dispari (M. Fiorentini, 2018);

Formula per una proprietà della funzione MCD, per a intero;

Formula per una proprietà della funzione MCD.

 

La funzione generatrice è Funzione generatrice della funzione MCD.

 

Alcune serie che coinvolgono la funzione MCD:

se Formula per la definizione di F(n), Serie che coinvolge la funzione MCD e in particolare Serie che coinvolge la funzione MCD e Serie che coinvolge la funzione MCD.

 

Nelle seguenti serie infinite la somma va calcolati sulle coppie di interi n e k primi tra loro:

Serie che coinvolge la funzione MCD;

Serie che coinvolge la funzione MCD;

Serie che coinvolge la funzione MCD;

Serie che coinvolge la funzione MCD;

Serie che coinvolge la funzione MCD.

Contattami

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