|
 L'
algoritmo Euclideo è un metodo sistematico di calcolo che
permette di determinare
in modo efficiente il massimo comune
divisore tra due numeri interi.
Dati due numeri interi esso consiste nell'effettuare:
- La divisione tra i due numeri assegnati;
- Le successive divisioni tra i divisori e i resti che man
mano si ottengono.
L'iterazione termina quando il resto della divisione tra i due
numeri è zero.
Il M.C.D. corrisponde al resto non nullo della divisione tra i
numeri assegnati. Osservazioni:
- due numeri interi,a e b, si dicono coprimi se M.C.D.(a,b)=1
- M.C.D.(a,b)=M.C.D.(b,r1), dove r1
è il resto della divisione tra a e b
- l'inverso dell'algoritmo di Euclide permette di scrivere il
M.C.D. come somma di due multipli di a e b , ossia
detta identità di Bezout
Applicazioni con
Excel Applicazioni con
Excel |
