Förstår inte euklides algoritm

Vilket steg är det du inte förstår i Wikipedias förklaring av Euklides algoritm?

Euklides algoritm är en algoritm för att bestämma största gemensamma delare till två heltal.

Förutsättning: Givet två heltal $a$ och $b$, där $a > b$.

• Om $b = 0$ är algoritmen klar och svaret är $a$.
• I annat fall beräknas $c$, där $c$ är resten när man delat $a$ med $b$.
• Sätt $a = b, b = c$ och börja om från punkt 1 igen, ($a$ får det värde $b$ har, och $b$ får det värde $c$ har).

Jag förstår att om a är större än b och b inte är en delare till a så måste SGD också vara SGD till resten som man får om man dividerar a med b, eftersom om a-r=b så måste a och b delare också dela r eftersom a=r+b. T.ex. a=100 och b=15. 100-15x6=10. Då måste SGD till a och b också vara SGD till r för annars skulle det inte gå att dela a med SGD. Det är stegen efter det i euklides algoritm då man fortsätter leta efter SGD till resten blir 0.

Från början hade du talen A = 100 och B = 15. Första steget ger resten 10. Då blir nästa steg A = 15 och B = 10. Vad blir nästa rest?

5

Förstår hur man använder den och varje steg men ej helheten

Nästa steg är alltså att A = 10 och B = 5. Resten blir 0, så SGD = 5. Alltså har vi visat att största gemensamma delare till 100 och 15 är 5.

Vad är det du inte förstår med helheten?

Den egenskap vi är ute efter bevaras vid varje steg, och tills vi är klara så minskar talen vid varje steg, så till slut uppnår vi det minsta möjliga talet med den önskade egenskapen.