ALGORITMUL EVKLIDA
EVROLIDA ALGORITMUL este o metodă pentru găsirea celui mai mare divizor comun de două numere întregi și, de asemenea, două polinoame într-o singură variabilă. Au a fost descris inițial în "Elementele" lui Euclid în formă geometrică ca o modalitate de a găsi măsura generală a două segmente. Au pentru a găsi cel mai mare divizor comun atât în inelul de întregi cât și în inelul de polinoame într-o variabilă este un caz special al unor algoritmi generali în inelele euclidiene.
Au pentru numere întregi este după cum urmează. Să, și. Împărțim restul prin - obținem un coeficient incomplet și un rest astfel de. Apoi împărțiți - obținem un coeficient incomplet și un rest. Acum împărțiți-vă și așa mai departe. Obținem un lanț de egalități:
în care, după un număr finit de pași, restul următor este egal cu zero, deoarece secvența de reziduuri este o secvență descrescătoare de întregi nonnegativi:
și, prin urmare, trebuie să se încheie într-un număr finit de pași cu zero. Apoi, cel mai mare divizor comun al numerelor este egal cu ultimul reziduu nenulos din schema divizării secvențiale (*).
Un exemplu. Găsiți cel mai mare divizor comun al numerelor 1981 și 378. Facem o diviziune secvențială:
Ultimul reziduu nonzero 7 este cel mai mare divizor comun al numerelor 1981 și 378.
Au pentru a găsi cel mai mare divizor comun de două polinoame și, de asemenea, constă în divizări succesive cu restul, apoi primul reziduu, apoi al doilea rest, și așa mai departe.
Deoarece gradele resturilor care sunt numere naturale scad, atunci după un număr finit de pași ajungem la un rest egal cu zero. Ultimul rest al nonzero este cel mai mare divizor comun al polinomilor u.
Articole similare
Trimiteți-le prietenilor: