Algoritme van Euclides: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Regel 29:
——————————————————————————————————
Een iets ander bewijs, dat ik wat concreter/
Lemma als n een deler is van A,B dan is n een deler van ggd(A,B).
Regel 43:
Er geldt ggd(A,B)=ggd(B,r(0))
Immers stel dat n=ggd(B,r(0)) A=q(0)b+r(0) --> (A/n=q(0)B/n)+(r(0)/n) q(0)B/n, en r(0)/n zijn geheel --> A/n is geheel.
Omgekeerd: laat m=ggd(A,B) dan
A-qB=r(0) --> A/m-qB/m-->r(0)/m en A/m en (q(0)B/m) zijn beide geheel, dus is r(0)/m het ook. Dus ggd(A,B) is deler van zowel r(0) als B en dus ook van ggd(B,r(0))
ggd(A,B) is deler van ggd(B,r(0)) en ggd(B,r(0)) is deler van ggd(A,B) dus geldt ggd(A,B)=ggd(B,r(0)).
Je hebt nu dus
Op analoge wijze krijg je steeds kleinere getallen:
| |||