Forstå Euklids algoritme

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderators: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

Post Reply
Realist1
Euclid
Euclid
Posts: 1993
Joined: 30/01-2007 20:39

Da var det min tur til å spørre dere til råds. :D
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. :D
daofeishi
Tyrann
Tyrann
Posts: 1486
Joined: 13/06-2006 02:00
Location: Cambridge, Massachusetts, USA

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.
Post Reply