Pagina lui Barnabas Harasztos

0 rămas, algoritmul s-a încheiat. Cel mai mare dealer comun ultimul rezidu diferit de zero - în cazul nostru 3.

rest diferit

Două întrebări importante apar (la fel ca în cazul tuturor algoritmilor):

  1. Este sigur că algoritmul se va termina?
  2. Realizează cu adevărat ceea ce ne așteptam? (A lnko-t.)

Răspuns la întrebarea 1: Deoarece restul din diviziunea reziduală este întotdeauna mai mic decât divizorul, \ [b> m_1> m_2> m_3> m_4 \ ldots, \] adică secvența reziduurilor este strict epuizată monoton. Deoarece există doar un număr finit (în special \ (b \) db) în \ (\ mathbb N \) sub \ (b \), această pierdere în greutate nu poate dura la nesfârșit. Altfel nu se poate opri, doar pentru ca restul de 0 \ (\ Longrightarrow \) din algoritm să se termine (terminal).

Răspuns la întrebarea 2: E mai greu deja. De ce ultimul rest diferit de zero (\ (m_k \)) va fi cel mai mare divizor comun al celor două numere originale (\ (a \) și \ (b \))?

2.1. enunț: Ultimul divizor comun rezidual diferit de zero: Scrieți diviziunile rămase sub forma unui produs și apoi aflați cine dintre numerele din ultimul rest diferit de zero, \ (m_k \).

(Figura arată acest lucru într-un algoritm care se termină în 6 pași: făcând clic pe acesta se evidențiază numerele împărțite la ultimul rest diferit de zero, în cazul nostru \ (m_5 \).

(2) În ultima linie, \ (m_5 \) este înmulțit cu \ (h_6 \), astfel încât \ (m_4 \) este, de asemenea, împărțit la \ (m_5 \). (Clic!)

(3) Ultima linie s-a dovedit a împărți \ (m_4 \) și \ (m_5 \) la cinci \ (m_5 \).
Să transferăm aceste cunoștințe în penultima linie! (Faceți clic pe imagine!)

(4) În dreapta penultimei linii, ambii membri pot fi împărțiți cu \ (m_5 \), deci \ (m_3 \) poate fi împărțit și cu acesta. (Faceți clic pe imagine!)

(5) Deci, în partea dreaptă a celei de-a patra linii \ (m_3 \) și \ (m_4 \) pot fi împărțite la \ (m_5 \) (faceți clic), astfel încât stânga \ (m_2 \) poate fi, de asemenea, împărțită la aceasta (faceți clic).

(6) Astfel, în partea dreaptă a celei de-a treia linii, \ (m_2 \) și \ (m_3 \) pot fi împărțite la \ (m_5 \) (clicuri), astfel încât stânga \ (m_1 \) poate fi, de asemenea, împărțită la aceasta (clicuri).

(7) Deci, în partea dreaptă a celei de-a doua linii \ (m_1 \) și \ (m_2 \) pot fi împărțite la \ (m_5 \) (faceți clic), astfel încât stânga \ (b \) poate fi împărțită la aceasta (faceți clic).

(8) Astfel, în partea dreaptă a primei linii, \ (b \) și \ (m_1 \) pot fi împărțite la \ (m_5 \) (faceți clic), astfel încât stânga \ (a \) poate fi împărțită la aceasta ( clic).

Este ușor de văzut că, indiferent de numărul de pași ai algoritmului, ceea ce am spus aici este adevărat: ultimul rest diferit de zero împarte și \ (a \) și \ (b \), adică

ultimul rest diferit de zero este un divizor comun al \ (\ mathrm \) și \ (\ mathrm\).

2.2. enunț: Ultimul rest diferit de zero este mai mare sau egal cu toți divizorii comuni: Fie \ (d \) un divizor comun al numerelor \ (a \) și \ (b \): \ [d \ text< >\ mare | \ text< >un \ hphantom \ text \ hphantomd \ text< >\ mare | \ text< >b \]

Diviziunile reziduale de la produsul produsului și suma sunt acum scrise sub forma diferenței.

(Din nou la pasul 6, figura prezintă un algoritm de terminare: evidențiind în galben numerele pe care divizorul comun \ (d \) le împarte.)

(2) În prima linie, împarte ambii membri ai părții stângi cu \ (d \), deci împarte și partea dreaptă cu \ (m_1 \). (Clic!)

(3) Deci, în partea stângă a celei de-a doua linii împarte \ (b \) și \ (m_1 \) la \ (d \) (faceți clic), deci și \ (m_2 \) în dreapta (faceți clic).

(4) În partea stângă a celei de-a treia linii, împărțiți \ (m_1 \) și \ (m_2 \) la \ (d \) (faceți clic), astfel încât \ (m_3 \) din partea dreaptă (faceți clic).

(5) Împarte \ (m_2 \) și \ (m_3 \) în partea stângă a celei de-a patra linii cu \ (d \) (clic), deci și \ (m_4 \) în dreapta (clic).

(6) În partea stângă a celei de-a cincea linii, împărțiți \ (m_3 \) și \ (m_4 \) la \ (d \) (faceți clic), astfel încât \ (m_5 \) din partea dreaptă (faceți clic).

Și \ (m_5 \) a fost ultimul rest diferit de zero, adică: \ [d \ text< >\ mare | \ text< >m_5 \]

(Încă un clic și imaginea va deveni gri înapoi.)

În mod clar, indiferent de numărul de pași din algoritm, ceea ce am spus aici este adevărat: orice divizor comun al lui \ (a \) și \ (b \) împarte ultimul rest diferit de zero. Cu toate acestea, cel care împarte nu poate fi mai mare decât cel care împarte, adică \ [d \ le \ text \]

Deci, el este cel mai mare dealer comun.