Euklids algoritme

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning
Euklids metode til at finde den største fælles divisor (GCD) af to startlængder BA og DC, begge defineret som multipla af en fælles "enhedslængde". Længden DC er kortere, det bruges til at "måle" BA, men kun én gang, fordi resten EA er mindre end DC. EA måler nu (to gange) den kortere længde DC, med resten FC kortere end EA. Derefter måler FC (tre gange) længde EA. Fordi der ikke er nogen rest, ender processen med, at FC er GCD. Til højre Nicomachus' eksempel med nummer 49 og 21 resulterende i deres GCD på 7 (afledt af Heath 1908: 300).

I matematik er den Euklids algoritme eller den Euklidske algoritme[note 1] en effektiv metode til at beregne den største fælles divisor (GCD efter greatest common divisor på engelsk, alternativt SFD) af to tal, det største tal der går op i begge tal. Det er opkaldt efter den antikke 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 en del af mange andre talteoretiske og kryptografiske beregninger.

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 GCD for 252 og 105 (som 252 = 21 × 12 og 105 = 21 × 5), og det samme tal, 21, er også GCD 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 GCD for de oprindelige to numre. Ved at vende processen på hovedet, kan GCD udtrykkes som en sum af de to originale tal, der hver gang ganges med et positivt eller negativt heltal, f.eks. 21 = 5 × 105 + (−2) × 252. Det at GCD altid kan udtrykkes på denne måde er kendt som Bézouts identitet.

Den version af Euklids algoritme, der er beskrevet ovenfor (og af Euklid), kan tage mange trin for at finde GCD, når et af de givne numre er meget større end det andet. En mere effektiv version af algoritmen tager en genvej, og i stedet for 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.

Euklids algoritme har mange teoretiske og praktiske anvendelser. Det bruges til at gøre brøker uforkortelige, og til 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 det 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 abstrakte algebra såsom Euklidiske ringe.

Baggrund: største fælles divisor[redigér | redigér wikikode]

Euklids algoritme beregner den største fælles divisor (GCD eller SFD) af to naturlige tal a og b. Den største fællesdivisor g er det største naturlige tal, hvor der ikke er nogen rest, når man dividerer a og b med tallet. Synonymer til GCD inkluderer den største fælles faktor (GCF), den højeste fælles faktor (HCF), den højeste fælles divisor (HCD) og den største fælles mål (GCM), alle med deres engelske forkortelser. Den største fælles divisor skrives ofte som gcd(a,b) eller base som (a,b), [1] skønt den sidstnævnte notation er tvetydig da den også bruges for et ideal i heltalsringenen, som er tæt knyttet til GCD.

Hvis gcd(a,b) = 1, så siges a og b at være indbyrdes primisk.[2] Denne egenskab indebærer ikke, at a eller b i sig selv er primtal.[3] For eksempel er hverken 6 eller 35 et primtal, da de begge har to primfaktorer: 6   =   2   ×   3 og 35   =   5   ×   7. Ikke desto mindre er 6 og 35 indbyrdes primiske. Intet andet naturligt antal end 1 går op i både 6 og 35, da de ikke har nogen primfaktorer til fælles.

"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."
Et 24 x 60 rektangel er dækket med ti 12 x 12 firkantede fliser, hvor 12 er GCD for 24 og 60. Mere generelt kan et a-gange-b rektangel være dækket med firkantede fliser i sidelængde c kun hvis c er en fælles divisor af a og b .

Lad g = gcd ( a,   b ). Da a og b begge er multipla af g, kan de skrives a   =   mg og b   =   ng, og der er ikke et større tal G   >   g, som dette er sandt for. De naturlige tal m og n skal være indbyrdes primiske, da enhver fælles faktor ellers ville kunne flyttes ud af m og n for at gøre g større. Derfor skal ethvert andet tal c, der går op i både a og b, også gå op i g. Den største fælles divisor g af a og b er den unikke (positive) fælles divisor af a og b, der er deleligt med enhver anden fælles divisor c. [4]

Den største fælles divisor kan visualiseres som følger. [5] Forestil dig et rektangulært område a by b, og en hvilken som helst fælles divisor c, der går op i både a og b. Rektanglets sider kan opdeles i segmenter med længde c, der deler rektanglet i et gitter af firkanter med sidelængde c . Den største fællesdelere g er den største værdi af c, som dette er muligt for. Som illustration kan et rektangulært område 24 x 60 opdeles i et gitter med: 1 x 1 firkanter, 2 x 2 firkanter, 3 x 3 firkanter, 4 x 4 firkanter, 6 x 6 firkanter, eller 12 x 12 firkanter. Derfor er 12 den største fælles divisor af 24 og 60. Et 24 x 60 rektangulært område kan opdeles i et gitter med 12 x 12 kvadrater med to firkanter langs den ene kant (24/12   =   2) og fem firkanter langs den anden (60/12   =   5).

GCD for to tal a og b er produktet af de primfaktorer, de to tal har til fælles, hvor den samme primfaktor kan bruges flere gange, men kun så længe produktet af disse faktorer deler både a og b . [6] F.eks. eftersom 1386 kan primtalsopløses til 2   ×   3   ×   3   ×   7   ×   11 og 3213 kan primtalsopløses til 3   ×   3   ×   3   ×   7   ×   17, er den største fælles divisor af 1386 og 3213 netop 63   =   3   ×   3   ×   7, produktet af deres fælles primtalsfaktorer. Hvis to tal ikke har nogen primtalsfaktorer til fælles, er deres største fælles divisor 1 (som her kommer fra det tomme produkt), med andre ord de er indbyrdes primiske. En vigtig fordel ved den Euklids algoritme er, at den kan finde GCD effektivt uden at skulle beregne primtalsfaktorerne. [7] 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 [8]

En anden definition af GCD er nyttig i avanceret matematik, især ringteori.[9] Den største fælles divisor g af to tal a og b, som begger er forskellig fra nul, er også den mindste positive lineære kombinationer med heltalskoefficienter af de to tal, det vil sige det mindste positive tal i formen ua   +   vb hvor u og v er heltal. Mængden med alle lineære kombination med heltalskoefficienter af a og b, er faktisk det samme som mængden med alle multipler af g ( mg, hvor m er et heltal). I moderne matematisk sprog er det ideal der genereres af a og b lig det ideal der genereres af g alene (et ideal genereret af et enkelt element kaldes et hovedideal, og alle idealer af heltal er hovedidealer). Nogle egenskaber ved GCD er faktisk lettere at se med denne definition, for eksempel det faktum, at enhver fælles divisor af a og b også deler den største fælles divisor (den deler begge udtryk for ua   +   vb ). Ækvivalensen af denne GCD-definition med de andre definitioner er beskrevet nedenfor.

Den største fælles divisor af tre eller flere tal er lig med produktet af de primfaktorer, der er fælles for alle numrene, [10] men det kan også beregnes ved gentagne gange at beregne GCD af talpar.[11] F.eks.

gcd(abc) = gcd(a, gcd(bc)) = gcd(gcd(ab), c) = gcd(gcd(ac), b).

Således er Euklidsalgoritme, der beregner GCD for to heltal, tilstrækkelig til at beregne GCD for vilkårligt mange heltal.

Beskrivelse[redigér | redigér wikikode]

Procedure[redigér | redigér wikikode]

Euklids algoritme foregår i en række trin, således at outputtet fra hvert trin bruges som input til det næste. Lad 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 k   =   0, det næste trin svarer til k   =   1 osv.

Hvert trin begynder med to ikke-negative rester r k − 1 og r k − 2 . Da algoritmen sikrer, at resterne falder støt med hvert trin, er r k − 1 mindre end dens forgænger r k − 2 . Målet med k'te skridt er at finde en kvotient q k og resten r k, der opfylder ligningen

og hvor der skal gælde at 0 ≤r k   <   r k − 1. Med andre ord fratrækkes det mindste tal r k − 1 gentagne gange fra det største tal r k − 2, indtil resten r k er mindre end r k − 1 .

I det indledende trin ( k   =   0) er resterne r −2 og r −1 er lig med a og b, de tal som GCD søges for. I det næste trin ( k   =   1) er resterne b og resten r 0 i det indledende trin, og så videre. Algoritmen kan således skrives som en sekvens af ligninger

Hvis a er mindre end b, vil det første trin i algoritmen bytte om på numrene. For eksempel, hvis a   <   b vil den oprindelige kvotient q 0 være nul, og resten r 0 være a. Således er r k mindre end sin forgænger r k −1 for alle k   ≥   0.

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

Bevis for korrekthed[redigér | redigér wikikode]

Gyldigheden af Euklids algoritme kan bevises ved et to-trins argument.[13] I det første trin vises at endelige resterende r N −1, der altså er forskellig fra nul, går op i både a og b . Da det er en fælles divisor, skal den være mindre end eller lig med den største fælles divisor g . I det andet trin vises det, at enhver fælles divisor af a og b, inklusive g, skal gå op i r N −1, og derfor skal g være mindre end eller lig med R N −1 . Disse to konklusioner betyder sammen at r N −1   =   g .

For at vise at r N −1 går op i både a og b (det første trin), ses først at R N −1 går op i sin forgænger r N −2

rN−2 = qN rN−1

da den sidste rest r N er nul. r N −1 går også op i den næste forgænger r N −3

rN−3 = qN−1 rN−2 + rN−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 r N −1 går op i alle de foregående rester, inklusive a og b . Ingen af de foregående rester r N −2, r N −3 osv. går op i a og b, da de efterlader en rest. Da r N −1 er en fælles divisor af a og b, må r N −1   ≤   g .

I det andet trin vises det at ethvert naturligt tal c der går op i både a og b (med andre ord enhver fælles divisor af a og b), også går op i alle resterne rk. Per definition kan a og b skrives som multipla af c: a   =   mc og b   =   nc, hvor m og n er naturlige tal. Derfor går c op i den indledende rest r0, da r0 =   -en   -   q 0 b   =   mc   -   q 0 nc   =   ( m   -   q 0 n ) c . Et analogt argument viser at c også går op i de efterfølgende rester r 1, r 2 osv. Derfor skal den største fælles divisor g gå op i r N −1, hvilket indebærer, at g   ≤   r N −1 . Da den første del af argumentet viste det omvendte ( r N −1   ≤   g ) følger det, at g   =   r N −1 . Således er g den største fælles divisor af alle de efterfølgende par: [14]

g = gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = … = gcd(rN−2, rN−1) = rN−1.

Gennemregnet eksempel[redigér | redigér wikikode]

Animation in which progressively smaller square tiles are added to cover a rectangle completely.
Animation af Euklids algoritme baseret på substraktion. Den indledende rektangel har dimensioner a   =   1071 og b   =   462. Kvadrater i størrelse 462 × 462 anbringes inden i den, og efterlader et 462 × 147 rektangel. Dette rektangel belægges med 147 × 147 kvadrater, indtil der er et 21 × 147 rektangel tilbage, som så igen belægges, denne gang med 21 × 21 kvadrater, hvilket ikke efterlader noget udækket område. Det mindste firkantede størrelse, 21, er GCD for 1071 og 462.

Til illustration kan Euklids algoritme bruges til at finde den største fælles divisor af a   =   1071 og b   =   462. Til at begynde med trækkes 462 fra 1071, indtil resten er mindre end 462. Dettte kan gøres to gange ( q 0   =   2), hvilket efterlader en rest af 147:

1071 = 2 × 462 + 147.

Derefter trækkes 147 fra 462, indtil resten er mindre end 147. Det kan gøres tre gange ( q 1   =   3), hvilket efterlader en rest af 21:

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

Da den sidste rest er nul, slutter algoritmen med 21 som den største fælles divisor for 1071 og 462. Dette stemmer overens med gcd(1071, 462), som beregnet overfor ved hjælp af primfaktorisering. I tabelform er trinnene:

Trin 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; algoritmen slutter

Visualisering[redigér | redigér wikikode]

Euklids algoritme kan visualiseres ved hjælp af den flisebelagte analogi, der er givet ovenfor for den største fælles divisor. Antag, at vi ønsker at dække et a x b rektangel med firkantede fliser nøjagtigt, 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 x b fliser, men dette efterlader en resterende r0 x b rektangel ubelagt, hvor r 0   <   b . Vi forsøger derefter at fliselægge den resterende rektangel med kvadratiske r0 x r0 fliser. Dette efterlader et andet rektangel r1 x r0 ubelagt, som vi forsøger at fliselægge vha. kradratiske r1 x r 1 fliser, og så videre. Sekvensen slutter, når der ikke er noget resterende rektangel, dvs. når de kvadratiske fliser dækker hele det forrige rektangel. Sidelængden på den mindste flise er GCD for dimensionerne på det originale rektangel. For eksempel er den mindste firkantede flise i den tilstødende figur 21 x 21 (vist i rødt), og 21 er GCD for 1071 og 462, dimensionerne på det originale rektangel (vist i grønt).

Division med rest[redigér | redigér wikikode]

Ved hvert trin k beregner Euklids algoritme en kvotient qk og resten rk fra to tal rk−1 og rk−2

rk−2 = qk rk−1 + rk

hvor rk er ikke-negativ og strengt mindre end størrelsenr k −1. Dette kaldes division med rest. Den matematiske sætning der ligger bag division med reste, er at en sådan kvotient og resten altid findes og er unikke.[15]

I Euklids originale version af algoritmen findes kvotienten og resten ved gentagen subtraktion; dvs. r k −1 trækkes fra rk −2, indtil resten r k er mindre end r k −1 . Derefter byttes der om på r k og rk−1 (så rk næste gang trækkes fra rk−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 moduloperationen, der kun giver resten. Således bliver hver iteration af Euklids algoritme simpelthen

rk = rk−2 mod rk−1.

Implementeringer[redigér | redigér wikikode]

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

function gcd (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, rk-2. Trinnet b := a mod b svarer til ovennævnte rekursionsformel r kr k −2 mod r k −1 . Den midlertidige variabel t holder værdien af rk-1 mens den næste rest r k beregnes. Ved slutningen af løkke-iterationen indeholder variablen b resten rk, mens variablen a holder sin forgænger, rk−1 .

I den subtraktionsbaserede version, der var Euklids originale version, er beregningen b = a mod b erstattet af gentagen subtraktion.[17] 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 gcd(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økken iteration, er a reduceret med tidligere rest b, indtil a er mindre end b. Så er a den næste resten r k . Derefter reduceres b med a, indtil det igen er mindre end a, hvilket giver den næste resten r k +1, og så videre.

Den rekursive version [18] er baseret på at to rester efter hinanden alle har samme GDC, samt stoptilstanden gcd ( r N −1,   0)   =   r N −1 .

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

Noter[redigér | redigér wikikode]

  1. ^ I nogle populære lærebøger, så som I. N. Hersteins Topics in Algebra og Serge Langs Algebra, refererer den engelske term "Euclidean algorithm" til division med rest.

Kildehenvisninger[redigér | redigér wikikode]

  1. ^ Stark 1978, s. 16
  2. ^ Stark 1978, s. 21
  3. ^ LeVeque 1996, s. 32
  4. ^ LeVeque 1996, s. 31
  5. ^ . ISBN 0-02-348331-8.  Manglende eller tom |title= (hjælp)
  6. ^ Schroeder 2005, s. 21–22
  7. ^ Schroeder 2005, s. 19
  8. ^ Schroeder 2005, s. 216–219
  9. ^ LeVeque 1996, s. 33
  10. ^ Stark 1978, s. 25
  11. ^ Ore 1948, s. 47–48
  12. ^ Stark 1978, s. 18
  13. ^ Stark 1978, s. 16–20
  14. ^ Knuth 1997, s. 320
  15. ^ Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. John Wiley & Sons, Inc. s. 270-271. ISBN 978-0-471-43334-7. 
  16. ^ Knuth 1997, s. 319–320
  17. ^ Knuth 1997, s. 318–319
  18. ^ Stillwell 1997, s. 14

[[Kategori:Pages with unreviewed translations]]