Euklids algoritme - største fælles divisor

Man har

        (13,8) = (8,5) = (5,3) = (3,2) = (2,1) = (1,1) = 1

Man stopper, når de to tal er lige store.

Ah, ok..

Men mine udregninger, - de er da korrekte, ikke?

#2

Jo, til og med linien med (1,2) .

(13,8)   idet   13= 1*8+5

= (8,5)    -     8 = 1*5+3

=(5,3)   -    5= 1*3+2

= (3,2)  -     3=1*2+1

= (2,1)     -    2=2*1+0

hvordan kommer 1,1 ind?

#4

2 erstattes af differensen 2-1 .

Til sidst har du, at 2 = 1·1 + 1 .

(13,8)   idet   13= 1*8+5

= (8,5)    -     8 = 1*5+3

=(5,3)   -    5= 1*3+2

= (3,2)  -     3=1*2+1

= (1,1)     -    2=1*1+1

= 1 

Er det således? det er godt nok en bøvlet måde at gøre tingene på. 
Og tusind tak for hjælpen!!

#6

Nej, det skal være    = (2,1)    i næstsidste ligningslinie.

Hvad mener du med bøvlet?

(13,8)   idet   13= 1*8+5

= (8,5)    -     8 = 1*5+3

=(5,3)   -    5= 1*3+2

= (3,2)  -     3=1*2+1

= (2,1)     -    2=1*1+1

= 1 

Dvs sådan? 

Jah, altså for en der ikke gør sig god i matematik, virker det bare sindsygt at bruge sådan en langsommelig metode til at dividere :S hehe

#8

Ja, sådan.

Nu er der jo tale om lidt mere end almindelig division. Man finder den største fælles divisor for to naturlige tal.

I øvrigt tog min opstilling

        (13,8) = (8,5) = (5,3) = (3,2) = (2,1) = (1,1) = 1

ikke ret lang tid at komme igennem. I hvert trin erstatter man det største tal med differensen mellem de to tal.

Tusind tak! Virkelig!

Nu sidder jeg med Landrocks bog omkring kryptologi, og de forkringler bare alt. Kan godt se hvad du mener, men i bogen går der bare volapyk i det hele. Det er godt nok svært synes jeg :S

#10

Jeg ved ikke, om informationen i dette link http://ramskovsressourcer.dk/undervisning/kryptologi/ressourcer/index.php

kan være til hjælp. Der er tilsyneladende nogle noter, der knytter sig til den bog, du omtaler.