GCD for 1020 og 330

Du har følgendende proces

1020=3*330+30
330=11*30+0

Altså er gcd(1020,330)=30

Er det så enkelt ? Der står i min opgave at jeg skal bruge Euclids algoritme til at finde svaret ?.. 

Det er Euklids Algoritme, som jeg har benyttet mig af. Tjek definitionen af den i din bog :)

Okay tak :) Det virker bare mere kompliceret i min bog end du for det til at lyde :) 

For nogle tal kan processen godt være lang, men for at lære den at kende skal du bare sætte dig ned og øve dig med to tilfældige tal.

Altså hvad jeg har gjort er at jeg har fundet ud af hvor mange gange 330 går op i 1020 og så skrive resten, som er første trin i processen. Dernæst skal man finde ud af hvor mange gange resten går op i 330 og så finde resten. Men da 30 går op helt op i 330, så slutter processen der, og vi er færdige. Derfor er algoritmen så kort for de to angivne tal.

Ahhh.. Det giver en hel del mere mening end den der står i min bog (Discrete Mathematical Structures (DiMS) ISBN: 978-1-78434-346-0)

Et andet mindre spøgsmål er så, hvad er LCM så for de to tal ? Least commen multiplum. 

Aha. Den bog brugte jeg også under Diskret Matematik kurset, da jeg startede. Hadede også den bog, hvilket gjorde at jeg anskaffede mig Diskrete Mamatiske Metoder af Jesper Lützen (ISBN: 978-87-70781-91-6).

For at finde LCM så skal du betragte primfaktoriseringen af de to tal. Du har, at

330=2*3*5*11 og 1020=2²*3*5*17

Så er LCM tallet hvor den højeste potens af alle primtallene indgår i, altså i vores tilfælde LCM(330,1020)=2*3*5*11*17=11220

Tror ikke at det første svar rækker for hvad der forventes af opgaven.. det er opgave 1 i sættet.

Aha, det er sikkert vist i jeres bog hvordan man bruger Euklids Algoritme den anden vej.

Tag udgangspunkt i beregningen ovenfor. Så har du, at man skal betragte den nederste linje, som ikke har nul i rest. Altså er det den forreste linje. Dermed har du, at 30=1020-3*330.

Hmm jeg tror ikke jeg er helt med.. :/ 

Du skal finde et s og et t så 30=s*1020+t*330. Det er præcist det du gør ved at starte bagfra i Euklids algoritme.

Algoritmen giver

1020=3*330+30
330=11*30+0

Så for at finde ud af hvordan du kan skrive 30=s*1020+t*330 for hele tal s,t kan du betragte

1020=3*330+30. Ved så at isolere 30 får du, at 1020-3*330=30 og du har, at s=1 og t=-3 løser ligningen.

Okay, det giver god mening. Jeg har dog lige et spørgsmål. (-3) er bare et tal som du har valgt eller hvodan er du kommet frem til dette ? :) Det har været en stor hjælp! :D

Det kommer fra ligningen 1020-3*330=30. Vi kan jo også skrive den som 1*1020+(-3)*330=30. Deraf valget.
 

Okay. Tak :) Som sagt det er ret at man kan hendvænde sig til denne side og få hjælp ! Tusinde tak for hjælpen  :D