Algoritmo esteso di Euclide: differenze tra le versioni

Versione delle 10:38, 27 gen 2024

Versione attuale delle 03:36, 31 ott 2024

(Una versione intermedia di un altro utente non mostrate)

Riga 9:

== Descrizione ==

Dati due numeri interi ''a'' e ''b'' sono i due interi, l'[[algoritmo di Euclide]] permette di calcolare le sequenze <math>q_1,\ldots, q_k</math> dei quozienti e <math>r_0,\ldots, r_{k+1}</math> dei resti come segue:

:<math>\begin{align}

Riga 49:

Il calcolo procede con una serie di iterazioni ''i'' da 0 a ''k''. Si arresta quando è nullo il risultato nella colonna "resto" (alla riga 4 nell'esempio), per cui il massimo comun divisore è 1 e quindi 20 e 7 sono coprimi.

I coefficienti di Bézout sono i risultati nelle ultime due colonne della penultima riga. Infatti, è facile verificare che <math>ax + by = \operatorname{MCD}(a, b)</math> poiché <math>20 \times (-1) + 7 \times 3 = 1.</math>

I risultati delle ultime due colonne nell'ultima riga, 7 e −20, sono rispettivamente, segno a parte, i quozienti di 7 e 20 rispetto al massimo comun divisore 1.