Să începem prin a găsi cel mai mare divizor comun al lui 527 și 341 folosind algoritmul Euclidian standard ca încălzire:

Algoritmul standard este succint și simplu și va servi ca un mic ghid frumos pentru implementarea algoritmului extins.

Pentru Algoritmul Euclidian Extins vom lua a treia ecuație (în albastru), vom scădea 155(1) din ambele părți și vom face o mică rearanjare pentru a obține o ecuație echivalentă în care 31 este izolat.

În continuare, vom înlocui 155 cu 341-186(1), care poate fi găsit prin rezolvarea celei de-a doua ecuații pentru 155, ceea ce ne dă următoarele:

Acum să curățăm acest lucru. Asigurați-vă că distribuiți semnul negativ prin paranteză și înlocuiți 186 + 186 cu 186-2.

După cum ați observat, pur și simplu lucrăm în sens invers prin algoritmul standard. Va trebui să parcurgem acest proces încă o dată pentru a obține o ecuație care să implice 527 și 341, care este în cele din urmă obiectivul nostru.

Pentru a face acest lucru, înlocuiți 186 cu 527 – 341(1), care provine din prima ecuație atunci când rezolvăm pentru 186.

Simplificați din nou ecuația prin distribuirea lui 2 și combinarea în grupuri de 527 și 341.

Acum am exprimat 31 ca o combinație liniară a 527 și 341. Destul de tare, nu-i așa?

În plus, numărul de pe partea opusă a combinației liniare este cel mai mare divizor comun. Deci, în acest caz, 31 este cel mai mare divizor comun dintre 527 și 341.

Algoritmul Euclidian Extins este util pentru că oferă identitatea lui Bezout și evidențiază gcd.

Mulțumim pentru lectură!

.