Redigerer Euklids algoritme (avsnitt)

==Bakgrunn==

Fremgangsmåten som beskrives i algoritmen var sannsynligvis godt kjent på Euklids tid  tog ble omtalt som ''antanairesis''. Sannsynligvis stammer metoden helt tilbake til [[Babylonia|babylonerne]]. Den fremkommer på en naturlig måte når man skal måle nøyaktig en avstand med en målestav med kjent lengde, men uten noen finere inndeling. Men man kan merke av kortere lengder på denne.<ref name = Holme> A. Holme, ''Matematikkens historie'', Bind 1, Fagbokforlaget, Bergen (2002). ISBN 82-7674-678-0.</ref>

Hvis den søkte avstanden kalles ''a'' og målestaven har lengde ''b'', kan man si at denne utgjør den lengdeenhet man vil benytte. Man ønsker derfor å måle ''a'' i enheter av ''b'', det vil si forholdet ''a''/''b''. Dette tilsvarer da en [[divisjon (matematikk)|divisjon]], og man vil generelt ikke finne noe noe heltallig svar.

===Fremgangsmåte===

Først måler man hvor mange hele ganger ''q''<sub>0</sub> som ''b'' kan plasseres langs ''a''. Generelt vil det da oppstå en rest ''r''<sub>0</sub> < ''b''. Når denne er forskjellig fra null, sier man at målingen eller divisjonen ikke «går opp» og man har

: <math> a = q_0 b + r_0 </math>

I neste omgang bestemmer man hvor mange ganger ''q''<sub>1 </sub>avstanden ''r''<sub>0</sub> er inneholdt i ''b''. Det vil eventuelt gi en ny rest ''r''<sub>1</sub>,  og man har

: <math> b = q_1 r_0 + r_1 </math>

hvor nå  ''r''<sub>1</sub> < ''r''<sub>0</sub>. På denne måten fortsetter man og måler hvor mange ganger ''r''<sub>1</sub> er inneholdt i ''r''<sub>0</sub>,

: <math> r_0  = q_2 r_1 + r_2 </math>

Generelt vil man etter å ha gjentatt dette ''n'' ganger at

: <math> r_{n-1}  = q_{n+1} r_n + r_{n+1} </math>

Denne fremgangsmåten kan fortsette helt til restene er blitt forsvinnende små, og man er fornøydd med resultatet. Det kan da generelt skrives som en [[kjedebrøk]]. Stopper man for eksempel etter ''n'' = 2 ganger der man kan sette {{nowrap|''r''<sub>3</sub> {{=}} 0}}, vil man ha at {{nowrap|''r''<sub>2</sub> {{=}} ''r''<sub>1</sub>/''q''<sub>3</sub>}}. Innsatt i den forrige ligningen, har man da {{nowrap|''r''<sub>1</sub> {{=}} ''r''<sub>0</sub>&thinsp;/(''q''<sub>2</sub>  + 1/''q''<sub>3</sub>)}}. Herav kan så ''r''<sub>0</sub> bestemmes uttrykt ved lengden ''b''. Resultatet er da kjedebrøken {{nowrap|''a''/''b'' {{=}} [''q''<sub>0</sub>;''q''<sub>1</sub>,''q''<sub>2</sub>,''q''<sub>3</sub>]}} som utskrevet er

: <math>{a\over b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3}}} </math>

I prinsippet gir denne fremgangsmåten et resultat som kan bli så nøyaktig som man ønsker ved å foreta disse gjentagelsene lenge nok.<ref name = Ore> O. Ore, ''Number Theory and Its History'', Dover Publications, New York (1988). ISBN 0-486-65620-9.</ref>