matematikk.net

Da var det min tur til å spørre dere til råds.
Jeg har ingen problemer med å benytte Euklids algoritme og få riktig svar etcetc, men jeg forstår ikke hvorfor metoden fungerer? Er det noen som har noen kjappe tips som kan hjelpe? Liker å forstå alt jeg gjør, men her sa det stopp. Har ikke virkelig studert dette, men normalt tar jeg slike ting som et skudd, men denne gangen har forståelsen vært med tilbakeholden.

Takker for svar.

For å forstå dette, må du først tenke gjennom hvorfor dette stemmer:

Dersom x, y, a, b er heltall og x = ay + b, så er gcd(x,y) = gcd(y,b)

Prøv å bevise dette på egenhånd. Dette er første del av forståelse av algoritmen.