În timp ce algoritmul "ordinar" Euclid găsește pur și simplu cel mai mare divizor comun de două numere și algoritmul extins Euclid găsește, pe lângă GCD, și coeficienți și astfel încât:
Ie el găsește coeficienții prin care GCD-ul a două cifre este exprimat în termeni de numere în sine.
Nu este dificil să se introducă calculul acestor coeficienți în algoritmul euclidian, este suficient să se deducă formulele prin care se schimbă atunci când ne mișcăm de la pereche la pereche (vom desemna semnul procentual luând restul diviziunii).
Deci, hai să găsim soluția problemei pentru noua pereche:
și dorim să obținem o soluție pentru perechea noastră:
Pentru aceasta, convertiți valoarea:
Înlocuim acest lucru în expresia de mai sus pentru u și obținem:
și, realizând regruparea termenilor, obținem:
Comparând acest lucru cu expresia originală asupra necunoscutului și obținem expresiile necesare:
punerea în aplicare
Baza recursivă este cazul. Apoi GCD este egal, și, evident, coeficienții necesari și sunt egali și respectiv. În alte cazuri, soluția obișnuită funcționează, iar coeficienții sunt recalculați conform formulelor descrise mai sus.
Algoritmul euclidian avansat în această implementare funcționează corect chiar și pentru numere negative.
literatură
Articole similare
Trimiteți-le prietenilor: