Euklids algoritme

Euklids algoritme er en matematisk algoritme og iterativ metode. Det er en effektiv metode til at beregne den største fælles divisor (forkortet SFD eller GCD efter greatest common divisor). For to tal er SFD det største tal, der går op i begge tal. Algoritmen er opkaldt efter den græske matematiker Euklid, der først beskrev det i sine Elementer (ca. 300 f.Kr.). Det er et eksempel på en algoritme, en trin-for-trin-procedure til udførelse af en beregning i henhold til veldefinerede regler, og er en af de ældste algoritmer i almindelig brug. Den kan bruges til at forkorte brøker så meget som muligt og er blot en af mange talteoretiske og kryptografiske beregningsmetoder. En vigtig fordel ved Euklids algoritme er, at den kan finde SFD effektivt uden at skulle beregne primtalsfaktorerne.^[1] Faktorisering af store heltal antages at være et beregningsmæssigt meget vanskeligt problem, og sikkerheden i mange bredt anvendte kryptografiske protokoller er baseret på, at det er uoverkommeligt.^[2] Euklids algoritme, der beregner SFD for to heltal, er tilstrækkelig til at beregne SFD for vilkårligt mange heltal.^{[kilde mangler]}

Euklid som den flamske maler Justus van Gent (ca. 1410 - ca. 1480) forestillede sig ham omkring 1474.

Algoritmen

Euklids algoritme er baseret på princippet om, at den største fælles divisor af to tal ikke ændres, hvis det større tal erstattes af forskellen mellem de to tal. For eksempel er 21 SFD for 252 og 105 (eftersom 252 = 21 × 12 og 105 = 21 × 5), og det samme tal, 21, er også SFD for 105 og 252 - 105 = 147. Da denne erstatning formindsker det største af de to tal, giver gentagelse af denne proces successivt mindre talpar, indtil de to tal bliver ens. Når dette sker, er de SFD for de oprindelige to tal. Ved at invertere processen, kan SFD udtrykkes som en sum af de to originale tal, der ganges med et positivt eller negativt heltal, f.eks. 21 = 5 × 105 + (−2) × 252. Det, at SFD altid kan udtrykkes på denne måde, er kendt som Bézouts identitet.^{[kilde mangler]}

Den version af Euklids algoritme, der er beskrevet ovenfor (og af Euklid), kan tage mange trin for at finde SFD, når et af de givne tal er meget større end det andet. En mere effektiv version af algoritmen tager en genvej, hvor man i stedet erstatter det største af de to tal med dets rest, når det divideres med den mindste af de to (i denne version stopper algoritmen, når det største tal er deleligt med det mindste). Med denne forbedring kræver algoritmen aldrig flere trin end fem gange antallet af cifre (base 10) i det mindste heltal. Dette blev bevist af Gabriel Lamé i 1844 og markerer begyndelsen på kompleksitetsteori . Yderligere metoder til forbedring af algoritmens effektivitet blev udviklet i det 20. århundrede.^{[kilde mangler]}

Procedure

Euklids algoritme er en iterativ metode, således at outputtet fra hvert trin bruges som input til det næste. Lad ${\displaystyle k}$ være et helt tal, der tæller trinnene i algoritmen, og start med at tælle fra nul. Det første trin svarer således til ${\displaystyle k=0}$, det næste trin svarer til ${\displaystyle k=1}$ osv.

Hvert trin begynder med to ikke-negative rester ${\displaystyle r_{k-1}}$ og ${\displaystyle r_{k-2}}$. Da algoritmen sikrer, at resterne falder støt med hvert trin, er ${\displaystyle r_{k-1}}$ mindre end dens forgænger ${\displaystyle r_{k-2}}$. Målet med ${\displaystyle k}$'ne skridt er at finde en kvotient ${\displaystyle q_{k}}$ og resten ${\displaystyle r_{k}}$, der opfylder ligningen

${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$

og hvor der skal gælde at

${\displaystyle 0\leq r_{k}<r_{k-1}}$

Med andre ord fratrækkes det mindste tal ${\displaystyle r_{k-1}}$ gentagne gange fra det største tal ${\displaystyle r_{k-2}}$, indtil resten ${\displaystyle r_{k}}$ er mindre end ${\displaystyle r_{k-1}}$.

I det indledende trin (${\displaystyle k=0}$) er resterne ${\displaystyle r_{-2}}$ og ${\displaystyle r_{-1}}$ lig med ${\displaystyle a}$ og ${\displaystyle b}$, de tal, som SFD søges for. I det næste trin (${\displaystyle k=1}$) er resterne ${\displaystyle b}$ og resten ${\displaystyle r_{0}}$ i det indledende trin, og så videre. Algoritmen kan således skrives som en sekvens af ligninger

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\r_{0}&=q_{2}r_{1}+r_{2}\\r_{1}&=q_{3}r_{2}+r_{3}\\&\,\,\,\vdots \end{aligned}}}$

Hvis ${\displaystyle a}$ er mindre end ${\displaystyle b}$, vil det første trin i algoritmen bytte om på tallene. For eksempel, hvis ${\displaystyle a<b}$ vil den oprindelige kvotient ${\displaystyle q_{0}}$ være nul, og resten ${\displaystyle r_{0}}$ være ${\displaystyle a}$. Således er ${\displaystyle r_{k}}$ mindre end sin forgænger ${\displaystyle r_{k-1}}$ for alle ${\displaystyle k\geq 0}$.

Da resterne falder i hvert trin, men aldrig kan være negative, vil en rest ${\displaystyle r_{N}}$ til sidst blive lig med nul og så stopper algoritmen.^[3] Den sidste ${\displaystyle r_{N-1}}$, som er forskellig fra nul, er den største fælles divisor af ${\displaystyle a}$ og ${\displaystyle b}$. Tallet ${\displaystyle N}$ kan ikke være uendeligt, fordi der kun er et begrænset antal ikke-negative heltal mellem den oprindelige rest ${\displaystyle r_{0}}$ og 0.^{[kilde mangler]}

Bevis for korrekthed

Gyldigheden af Euklids algoritme kan bevises ved et to-trins argument.^[4] I det første trin vises, at den sidste rest ${\displaystyle r_{N-1}}$, der altså er forskellig fra nul, går op i både ${\displaystyle a}$ og ${\displaystyle b}$. Da det er en fælles divisor, skal den være mindre end eller lig med den største fælles divisor ${\displaystyle g}$. I det andet trin vises det, at enhver fælles divisor af ${\displaystyle a}$ og ${\displaystyle b}$, inklusiv ${\displaystyle g}$, skal gå op i ${\displaystyle r_{N-1}}$, og derfor skal ${\displaystyle g}$ være mindre end eller lig med ${\displaystyle r_{N-1}}$. Disse to konklusioner betyder sammen, at

${\displaystyle r_{N-1}=g}$

For at vise at ${\displaystyle r_{N-1}}$ går op i både ${\displaystyle a}$ og ${\displaystyle b}$ (det første trin), ses først, at ${\displaystyle r_{N-1}}$ går op i sin forgænger ${\displaystyle r_{N-2}}$

${\displaystyle r_{N-2}=q_{N}r_{N-1}}$

da den sidste rest ${\displaystyle r_{N}}$ er nul. ${\displaystyle r_{N-1}}$ går også op i den næste forgænger ${\displaystyle r_{N-3}}$

${\displaystyle r_{N-3}=q_{N-1}r_{N-2}+r_{N-1}}$

fordi den går op i begge led på højre side af ligningen. Ved at gentage dette argument igen og igen, ses det at ${\displaystyle r_{N-1}}$ går op i alle de foregående rester, inklusive ${\displaystyle a}$ og ${\displaystyle b}$. Ingen af de foregående rester ${\displaystyle r_{N-2}}$, ${\displaystyle r_{N-3}}$ osv. går op i ${\displaystyle a}$ og ${\displaystyle b}$, da de efterlader en rest. Da ${\displaystyle r_{N-1}}$ er en fælles divisor af ${\displaystyle a}$ og ${\displaystyle b}$, må

${\displaystyle r_{N-1}\leq g}$

I det andet trin vises det at ethvert naturligt tal c der går op i både ${\displaystyle a}$ og ${\displaystyle b}$ (med andre ord enhver fælles divisor af ${\displaystyle a}$ og ${\displaystyle b}$), også går op i alle resterne ${\displaystyle r_{k}}$. Pr. definition kan ${\displaystyle a}$ og ${\displaystyle b}$ skrives som multipla af ${\displaystyle c}$:

${\displaystyle {\begin{aligned}a&=mc\\b&=nc\end{aligned}}}$

hvor ${\displaystyle m}$ og ${\displaystyle n}$ er naturlige tal. Derfor går ${\displaystyle c}$ op i den indledende rest ${\displaystyle r_{0}}$, da

${\displaystyle r_{0}=a-q_{0}b=mc-q_{0}nc=(m-q_{0}n)c}$

Et analogt argument viser, at ${\displaystyle c}$ også går op i de efterfølgende rester ${\displaystyle r_{1}}$, ${\displaystyle r_{2}}$ osv. Derfor skal den største fælles divisor ${\displaystyle g}$ gå op i ${\displaystyle r_{N-1}}$, hvilket indebærer, at

${\displaystyle g\leq r_{N-1}}$

Da den første del af argumentet viste det omvendte (${\displaystyle r_{N-1}\leq g}$), følger det, at

${\displaystyle g=r_{N-1}}$

Således er ${\displaystyle g}$ den største fælles divisor af alle de efterfølgende par:^[5]

${\displaystyle g={\text{sfd}}(a,b)={\text{sfd}}(b,r_{0})={\text{sfd}}(r_{0},r_{1})=...={\text{sfd}}(r_{N-2},r_{N-1})=r_{N-1}}$

Gennemregnet eksempel

Animation af Euklids algoritme baseret på substraktion. Det indledende rektangel (grønt) har dimensionerne ${\displaystyle a=1071}$ og ${\displaystyle b=462}$. Kvadrater (orange) i størrelsen ${\displaystyle 462\times 462}$ anbringes inden i, hvilket efterlader et ${\displaystyle 462\times 147}$ rektangel. Dette rektangel belægges med ${\displaystyle 147\times 147}$ kvadrater (blå), indtil der er et ${\displaystyle 21\times 147}$ rektangel tilbage, som så igen belægges, denne gang med ${\displaystyle 21\times 21}$ kvadrater (røde), hvilket ikke efterlader noget udækket område. Den mindste firkantede størrelse, 21, er dermed SFD for 1071 og 462.

Til illustration kan Euklids algoritme bruges til at finde den største fælles divisor af ${\displaystyle a=1071}$ og ${\displaystyle b=462}$. Først trækkes 462 fra 1071 et antal gange indtil resten er mindre end 462. Dette kan gøres to gange (${\displaystyle q_{0}=2}$), hvilket efterlader en resten 147:

${\displaystyle 1071=2\times 462+147}$

Derefter trækkes 147 fra 462 et antal gange indtil resten bliver mindre end 147. I dette tilfælde kan det gøres tre gange ( q ₁   =   3), hvilket efterlader resten 21:

462 = 3 × 147 + 21.

Derefter trækkes 21 fra 147 nogle gange indtil resten er mindre end 21. Dette kan gøres syv gange ( q ₂   =   7) uden at efterlade nogen rest:

147 = 7 × 21 + 0.

Da den sidste rest er nul, slutter algoritmen med 21, som derfor er den største fælles divisor for 1071 og 462. Dette stemmer overens med sfd(1071, 462), som beregnet overfor ved hjælp af primfaktorisering. I tabelform ser er den herover beskrevne algoritme for talparret (1071, 462) sådan ud:

Trin ${\displaystyle k}$	Ligning	Kvotient og resten
0	1071 = q0 462 + r0	q0 = 2 og r0 = 147
1	462 = q1 147 + r1	q1 = 3 og r1 = 21
2	147 = q2 21 + r2	q2 = 7 og r2 = 0; resten er 0 og algoritmen slutter derfor her.

Visualisering

Euklids algoritme kan visualiseres ved hjælp af en analogi: Man skal forestille sig, at man skal afdække et område med fliser på den særlige måde, at man hele tiden vælger den størst mulige kvadratiske flise (de to sidelængder er som bekendt ens for en kvadratisk flise). Denne såkaldte "fliselæggermetode" er vist som animation på figuren, hvor det grønne område med sidelængderne a og b skal dækkes med kvadratiske fliser, og hvor a er det største af de to tal. Vi forsøger først at fliselægge rektanglet ved hjælp af kvadratiske b · b fliser, men dette efterlader en resterende r₀ · b rektangel ubelagt, hvor r ₀   <   b . Vi forsøger derefter at fliselægge den resterende rektangel med kvadratiske r₀ · r₀ fliser. Dette efterlader et andet rektangel r₁ · r₀ ubelagt, som vi forsøger at fliselægge med kvadratiske r₁ · r ₁ fliser. Vi fortsætter på samme måde. Sekvensen slutter, når der ikke er noget resterende rektangel, det vil sige, når de kvadratiske fliser dækker hele det forrige rektangel. Sidelængden på den mindste flise er SFD, det vil sige den Største Fælles Divisor, for dimensionerne på det originale rektangel. I eksemplet er den mindste kvadratiske flise i animationen 21 · 21 og disse fliser bliver vist med rød farve. Denne animation viser altså, at tallet 21 er SFD for talparret (1071, 462). Størrelsen af det originale rektangel er 1071 · 462 og er vist med grøn farve.

Division med rest

Ved hvert trin k beregner Euklids algoritme en kvotient ${\displaystyle q_{k}}$ og resten ${\displaystyle r_{k}}$ fra to tal ${\displaystyle r_{k-1}}$ og ${\displaystyle r_{k-2}}$

${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$

hvor ${\displaystyle r_{k}}$ er ikke-negativ og strengt mindre end størrelsen på ${\displaystyle r_{k-1}}$. Dette kaldes division med rest. Den matematiske sætning der ligger bag division med rest, er at en sådan kvotient og resten altid findes og er unikke.^[6]

I Euklids originale version af algoritmen findes kvotienten og resten ved gentagen subtraktion; dvs. ${\displaystyle r_{k-1}}$ trækkes fra ${\displaystyle r_{k-2}}$, indtil resten ${\displaystyle r_{k}}$ er mindre end ${\displaystyle r_{k-1}}$. Derefter byttes der om på ${\displaystyle r_{k}}$ og ${\displaystyle r_{k-1}}$ (så ${\displaystyle r_{k}}$ næste gang trækkes fra ${\displaystyle r_{k-1}}$), og processen gentages. Euklidisk opdeling reducerer alle trin mellem to opbytninger til et enkelt trin, hvilket er mere effektivt. Desuden er kvotienterne ikke nødvendige, så man kan erstatte division med rest med modulooperationen, der kun giver resten. Således bliver hver iteration af Euklids algoritme simpelthen

${\displaystyle r_{k}=r_{k-2}{\bmod {r}}_{k-1}}$

Implementeringer

Implementeringer af algoritmen kan udtrykkes i pseudocode . F.eks. kan den divisionsbaserede version programmeres som ^[7]

function sfd (a, b)
    while b ≠ 0
        t := b; 
        b := a mod b; 
        a := t; 
    return a; 

I begyndelsen af den k'te iteration indeholder variablen b den nyeste rest r_k-1, hvorimod variablen a holder dens forgænger, r_k-2. Trinnet b := a mod b svarer til ovennævnte rekursionsformel r _k ≡ r _{k −2} mod r _{k −1} . Den midlertidige variabel t holder værdien af r_k-1 mens den næste rest r _k beregnes. Ved slutningen af løkke-iterationen indeholder variablen b resten r_k, mens variablen a holder sin forgænger, r_k−1 .

I den subtraktionsbaserede version, der var Euklids originale version, er beregningen b = a mod b erstattet af gentagen subtraktion.^[8] I modsætning til den divisionsbaserede version, der fungerer med vilkårlige heltal som input, antager den subtraktionsbaserede version, at input består af positive heltal og stopper, når a = b :

function sfd(a,b)
    while a ≠ b
        if a > b
            a := a - b; 
        else
            b := b - a; 
    return a; 

Variablerne a og b veksler med de foregående rester r _{k −1} og r _{k −2} . Hvis a er større end b i begyndelsen af en iteration, så er a = r _{k -2,} eftersom r _{k -2} > r _{k -1.} I løbet af løkkens iteration, bliver a reduceret med den tidligere rest b, indtil a er mindre end b. Så er a den næste rest r _k . Derefter reduceres b med a, indtil det igen er mindre end a, hvilket giver den næste rest r _{k +1}, og så videre.

Den rekursive version ^[9] er baseret på at to rester efter hinanden alle har samme GDC, samt stoptilstanden sfd ( r _{N −1},   0)   =   r _{N −1} .

function gcd (a, b)
    if b = 0
        return a; 
    else
        return gcd(b, a mod b);

Anvendelser

Euklids algoritme har mange teoretiske og praktiske anvendelser. Den bruges til at gøre brøker uforkortelige og til at foretage division i kongruensregning. Beregninger, der bruger denne algoritme, indgår i kryptografiske protokoller, der bruges til at sikre internetkommunikation, og i metoder til at bryde disse kryptosystemer ved at primtalsfaktorisere store tal. Euklids algoritme kan bruges til at løse Diofantiske ligninger såsom at finde tal, der tilfredsstiller flere kongruenser samtidig som i den kinesiske restklassesætning til at konstruere kædebrøker og til at finde gode rationelle tilnærmelser til reelle tal. Endelig kan den bruges som et grundlæggende værktøj til at bevise sætninger i talteori såsom Lagranges fire-kvadratsætning, og at primtalsfaktoriseringer er unikke. Den originale algoritme blev kun beskrevet for naturlige tal og geometriske længder (reelle tal), men algoritmen blev generaliseret i det 19. århundrede til andre typer tal såsom Gaussiske heltal og polynomier i en variabel. Dette førte til udviklingen af koncepter i moderne abstrakt algebra såsom euklidiske ringe.^{[kilde mangler]}

Kildehenvisninger

1. Schroeder 2005, s. 19
2. Schroeder 2005, s. 216–219
3. Stark 1978, s. 18
4. Stark 1978, s. 16–20
5. Knuth 1997, s. 320
6. Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. John Wiley & Sons, Inc. s. 270-271. ISBN 978-0-471-43334-7.
7. Knuth 1997, s. 319–320
8. Knuth 1997, s. 318–319
9. Stillwell 1997, s. 14

Litteratur

• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3. udgave). Addison–Wesley. ISBN 0-201-89684-2.
• LeVeque, W. J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9.
• Ore, O. (1948). Number Theory and Its History. New York: McGraw–Hill.
• Schroeder, M. (2005). Number Theory in Science and Communication (4. udgave). Springer-Verlag. ISBN 0-387-15800-6.
• Stark, H. (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8.
• Stillwell, J. (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 0-387-95587-9.
• Stillwell, J. (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2.

Oversættelse

Denne artikel eller en tidligere version er helt eller delvist oversat fra den engelsksprogede Wikipedia, der er tilgængelig under Creative Commons Kreditering-Deling på samme vilkår 3.0. Se versionshistorik for oplysninger om oprindelig(e) bidragyder(e).