L’algoritmo standard è succinto e diretto e servirà da piccola guida per implementare l’algoritmo esteso.

Per l’algoritmo euclideo esteso prenderemo la terza equazione (in blu), sottrarremo 155(1) da entrambi i lati, e faremo una piccola riorganizzazione per fare un’equazione equivalente dove 31 è isolato.

Poi sostituiremo 155 con 341-186(1), che può essere trovato risolvendo la seconda equazione per 155, dandoci la seguente:

Ora puliamo questo. Assicuratevi di distribuire il segno negativo attraverso la parentesi e sostituite 186 + 186 con 186-2.

Come potete notare, stiamo semplicemente lavorando all’indietro attraverso l’algoritmo standard. Avremo bisogno di eseguire questo processo ancora una volta per ottenere un’equazione che coinvolga 527 e 341, che è in definitiva il nostro obiettivo.

Per fare questo sostituisci 186 con 527 – 341(1), che viene dalla prima equazione quando risolviamo per 186.

Semplificare ancora l’equazione distribuendo il 2 e combinando in gruppi di 527 e 341.

Abbiamo ora espresso 31 come combinazione lineare di 527 e 341. Forte, eh?

Inoltre il numero sul lato opposto della combinazione lineare è il più grande comune divisore. Quindi in questo caso 31 è il massimo comune divisore di 527 e 341.

L’algoritmo euclideo esteso è comodo perché fornisce l’identità di Bezout e mette in evidenza il gcd.

Grazie per aver letto!