Le proprietà dell’MCD

Riprendiamo l’argomento del Massimo Comun Divisore, o MCD , per aggiungere alla nostra borsa del matematico un procedimento essenziale: la tecnica di costruzione delle proprietà di un operatore.

A tempo debito, abbiamo definito la procedura ricorsiva per il calcolo dell’MCD sulla base di due semplici proprietà:

MCD(N,N) = N

MCD(N, M) = MCD(N-M, M)

Abbiamo visto che con queste due semplici proprietà è possibile calcolare l’MCD di qualsiasi coppia di numeri interi, applicando ricorsivamente le definizioni fino ad arrivare ad un valore univoco.

Quando abbiamo parlato dell’irrazionalità di radice di 2, non è stato possibile usare la funzione MCD perché avremmo dovuto esplicitare tutti i passaggi della ricorsione. Ci mancava un elemento fondamentale: l’elencazione delle proprietà dell’MCD. In questo post ci concentriamo sull’MCD come operatore e ne ricaviamo alcune proprietà.

Inziamo dalla più ovvia:

MCD(1, N) = 1

il massimo comun divisore di un numero qualsiasi ed 1 è, ovviamente, 1.

Questa è un pò meno ovvia:

MCD(N, 0) = N

zero, per definizione, è divisibile per tutti i numeri naturali e il risultato fa sempre zero. Per questo, il massimo numero naturale per cui è possibile dividere contemporaneamente zero ed N è, appunto, N.

Questa è un pò più complessa: se A è un intero qualsiasi, vale:

MCD(AN, AM) = A MCD(N,M)

risultato cui si arriva rapidamente applicando la definizione ricorsiva:

MCD(AN, AM) = MCD(A(N-M), AM) =

che, applicata fino alla condizione di terminazione, restituirà:

= MCD(A MCD(N,M), A MCD(N,M)) = A MCD(N.M)

Sappiamo infatti che MCD(N,M) è il massimo comun divisore di N ed M, e il fattore moltiplicativo A viene “portato dietro” durante il calcolo ricorsivo, grazie alle proprietà della moltiplicazione.

La stessa proprietà vale per la divisione, purché A sia un divisore comune di M ed N:

MCD(N/A, M/A) = MCD(N,M)/A

il procedimento è esattamente lo stesso, perché è possibile portare dietro il fattore 1/A attraverso tutto il procedimento ricorsivo (fatta salva l’ipotesi che A sia un divisore di entrambe).

Questa, invece, l’abbiamo già dimostrata nel post relativo alla irrazionalità di radice di 2:

MCD(N^K, M^K) = MCD(N,M)^K

dove K è una potenza intera qualsiasi.

Infine, una definizione che garantisce una condizione fondamentale, puramente astratta, ne riparleremo a proposito dell’algebra:

MCD(0, 0) = 0

A che serve tutto ciò ? Alla prossima.