Algoritmo di Euclide: differenze tra le versioni

Versione delle 12:08, 25 apr 2025

Versione attuale delle 13:09, 1 mag 2025

Riga 10:

Questo è noto con il nome di [[Algoritmo esteso di Euclide|algoritmo di Euclide esteso]].

Questi algoritmi possono essere usati, oltre che con i [[numeri interi]], in ogni contesto in cui è possibile eseguire lal'operazione di divisione colcon resto. Ad esempio, l'algoritmo funziona per i [[polinomio|polinomi]] ad una indeterminata su un [[campo (matematica)|campo]] ''K'', o polinomi omogenei a due indeterminate su un campo, o gli [[intero gaussiano|interi gaussiani]]. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato [[anello euclideo]].

Euclide originariamente formulò il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il più corto dal più lungo. Questo procedimento è equivalente alla implementazione seguente, che è molto meno efficiente del metodo indicato sopra.