|
# Wanneer er 0 overblijft, is ''B'' de ggd.
# Zo niet, herhaal dan het algoritme met ''B'' en wat er van ''A'' over is.
Een ander bewijs:
Lemma als n een deler is van A,B dan is n een deler van ggd(A,B).
Dit is direct duidelijk als je A en B ontbindt in priemfactoren.
Nu verder:
ggd(A,B) met A >B.
A=q(0)B+r(0), met r(0) < B (delen met rest) met A, B, q(0) en r(0) natuurlijke getallen ongelijk 0.
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. Dus n=ggd(B,r(0)) is deler van zowel A als B dus geldt ggd(B,r(0)) deler van ggd(A,B)
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 kleinere getallen waarvan je de ggd moet bepalen.
Op analoge wijze krijg je steeds kleinere getallen:
A=q(0)B+r(0) met A>B>r(0)
B=q(1)r(0)+r(1) met B>r(0)>r(1)
r(0)=q(2)r(1)+r(2) met r(0)>r(1)>r(2)
...
...
...
Dit stopt een keer, omdat we met twee eindige getallen zijn begonnen en we dus maar een eindig aantal keren het deel met rest uit kunnen voeren.
Bij de laatste stap hebben we:
r(n)=(q(n+2)).r(n+1)+r(n+2) waar r(n+2)=0 en r(n+1) de ggd(A,B)
Voorbeeld:
ggd(42,30) ( A=32, B=30)
42=30+12 ( A=42, B=30, q(0)=1, r(0)=12)
30=2*12+6 (B=30, q(1)=2, r(0)=12, r(1)=6)
12=2*6+0 (r(0)=12, q(2)=2, r(1)=6, r(2)=0) ggd(40,32)=6.
== Voorbeeld ==
| 