Algoritmo esteso di Euclide: differenze tra le versioni

Versione delle 10:35, 27 gen 2024

Versione attuale delle 03:36, 31 ott 2024

(3 versioni intermedie di un altro utente non mostrate)

Riga 1:

{{S|matematica|crittografia}}

In [[aritmetica]] e nella [[Programmazione (informatica)|programmazione]] l{{'}}'''algoritmo esteso di Euclide''' è un'estensione dell'[[algoritmo di Euclide]] che calcola non solo il [[massimo comun divisore]] (indicato con MCD nel seguito) tra due interi ''a'' e ''b'', ma anche i coefficienti ''x'' e ''y'' dell'[[identità di Bézout]].

Riga 11 ⟶ 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 51 ⟶ 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.

Riga 110 ⟶ 108:

[[Categoria:Euclide]]

[[Categoria:Algoritmi aritmetici|Euclide]]