Forskel mellem versioner af "Euklids algoritme"

13 bytes tilføjet ,  for 3 måneder siden
m
lidt tegnsætning og sprog
(skifter illustration, fordi den er uforståelig, se diskussionssiden)
m (lidt tegnsætning og sprog)
 
== Algoritmens princip ==
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 [[Euklids udvidede algoritme|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]].
 
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 [[Division med rest|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 ([[Grundtal|base]] 10) i det mindste heltal. Dette blev bevist af [[Gabriel Lamé]] i 1844 og markerer begyndelsen på [[Tidskompleksitet|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 at foretage [[Division (matematik)|division]] i [[kongruensregning]]. Beregninger, der bruger denne algoritme, indgår i [[kryptografi]]ske protokoller, der bruges til at sikre [[internet]]kommunikation, og i metoder til at bryde disse kryptosystemer ved at [[Primtalsopløsning|primtalsfaktorisere]] store tal. Euklids algoritme kan bruges til at løse [[Diofantisk ligning|Diofantiske ligninger]], såsom at finde tal, der tilfredsstiller flere kongruenser samtidig som i den [[kinesiske restklassesætning]], til at konstruere [[kædebrøk]]er, og til at finde gode [[Diofantisk approksimation|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 [[Aritmetikkens fundamentalsætning|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 helttal|Gaussiske heltal]] og [[Polynomium|polynomier]] i en variabel. Dette førte til udviklingen af koncepter i moderne [[abstrakt algebra]] såsom [[Euklidisk ring|euklidiske ringe]].
 
== Baggrund: største fælles divisor ==
Euklids algoritme beregner den [[største fælles divisor]] (GCD eller SFD) af to [[Naturligt tal|naturlige tal]] ''a'' og ''b''. Den største fælles divisor ''g'' er det største naturlige tal, hvor der ikke er nogen rest, når man dividerer ''a'' og ''b'' med tallet. Synonymer til ''største fælles divisor'' er den ''største fælles faktor'' og det ''største fælles mål''. Den største fælles divisor skrives ofte som sfd(''a'',''b'') eller base som (''a'',''b''),<ref>{{Harvnb|Stark|1978|p=16}}</ref> skønt den sidstnævnte notation er tvetydig, da den også bruges for et [[Ideal (ringteori)|ideal]] i heltalsringen, som er tæt knyttet til SFD.
 
Hvis sfd(''a'',''b'') = 1, så siges ''a'' og ''b'' at være [[indbyrdes primisk]]e.<ref>{{Harvnb|Stark|1978|p=21}}</ref> Denne egenskab indebærer ikke, at ''a'' eller ''b'' i sig selv er [[primtal]].<ref>{{Harvnb|LeVeque|1996|p=32}}</ref> For eksempel er hverken 6 eller 35 primtal, da de begge har to primfaktorer: 6 &nbsp; = &nbsp; 2 &nbsp; × &nbsp; 3 og 35 &nbsp; = &nbsp; 5 &nbsp; × &nbsp; 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.
Lad ''g'' = sfd ( ''a'', &nbsp; ''b'' ). Da ''a'' og ''b'' begge er multipla af ''g'', kan de skrives ''a'' &nbsp; = &nbsp; ''mg'' og ''b'' &nbsp; = &nbsp; ''ng'', og der er ikke et større tal ''G'' &nbsp; > &nbsp; ''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''. <ref>{{Harvnb|LeVeque|1996|p=31}}</ref>
 
Den største fælles divisor kan visualiseres som følger:<ref>{{cite book | last = Grossman|first= J. W. | year = 1990 | title = Discrete Mathematics | publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = 213}}</ref> ForestilTag digudgangspunkt i et rektangulært område ''a'' gange ''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ællesdeler ''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 &nbsp; = &nbsp; 2) og fem firkanter langs den anden (60/12 &nbsp; = &nbsp; 5).
 
SFD 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''. <ref name="Schroeder_21">{{Harvnb|Schroeder|2005|pp=21–22}}</ref> F.eks. eftersom 1386 kan primtalsopløses til 2 &nbsp; × &nbsp; 3 &nbsp; × &nbsp; 3 &nbsp; × &nbsp; 7 &nbsp; × &nbsp; 11 og 3213 kan primtalsopløses til 3 &nbsp; × &nbsp; 3 &nbsp; × &nbsp; 3 &nbsp; × &nbsp; 7 &nbsp; × &nbsp; 17, er den største fælles divisor af 1386 og 3213 netop 63 &nbsp; = &nbsp; 3 &nbsp; × &nbsp; 3 &nbsp; × &nbsp; 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 er de indbyrdes primiske. En vigtig fordel ved Euklids algoritme er, at den kan finde SFD effektivt uden at skulle beregne primtalsfaktorerne.<ref>{{Harvnb|Schroeder|2005|p=19}}</ref> [[Primtalsopløsning|Faktorisering]] af store heltal antages at være et beregningsmæssigt meget vanskeligt problem, og sikkerheden i mange bredt anvendte [[Kryptografisk protokol|kryptografiske protokoller]] er baseret på, at det er uoverkommeligt.<ref name="Schroeder_216">{{Harvnb|Schroeder|2005|pp=216–219}}</ref>
 
En anden definition af SFD er nyttig i avanceret matematik, især [[Ring (matematik)|ringteori]].<ref name="Leveque_p33">{{Harvnb|LeVeque|1996|p=33}}</ref> Den største fælles divisor ''g'' af to tal ''a'' og ''b'', som begge er forskellig fra nul, er også den mindste positive lineære kombination med heltalskoefficienter af de to tal, det vil sige det mindste positive tal i formen ''ua'' &nbsp; + &nbsp; ''vb'' hvor ''u'' og ''v'' er heltal. [[Mængde]]n med alle lineære kombinationer med heltalskoefficienter af ''a'' og ''b'' er faktisk den samme som mængden med alle multipler af ''g'' ( ''mg'', hvor ''m'' er et heltal). I moderne matematisk sprog er det [[Ideal (ringteori)|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 SFD 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'' &nbsp; + &nbsp; ''vb'' ). Ækvivalensen af denne SFD-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 tallene, <ref>{{Harvnb|Stark|1978|p=25}}</ref> men det kan også beregnes ved gentagne gange at beregne SFD af talpar.<ref>{{Harvnb|Ore|1948|pp=47–48}}</ref> F.eks.
Hvis ''a'' er mindre end ''b'', vil det første trin i algoritmen bytte om på tallene. For eksempel, hvis ''a'' &nbsp; < &nbsp; ''b'' vil den oprindelige kvotient ''q'' <sub>0</sub> være nul, og resten ''r'' <sub>0</sub> være ''a''. Således er ''r'' <sub>''k''</sub> mindre end sin forgænger ''r'' <sub>''k'' −1</sub> for alle ''k'' &nbsp; ≥ &nbsp; 0.
 
Da resterne falder i hvert trin, men aldrig kan være negative, vil en rest ''r'' <sub>''N''</sub> til sidst blive lig med nul og så stopper algoritmen.<ref>{{Harvnb|Stark|1978|p=18}}</ref> Den sidste ''r'' <sub>''N'' −1</sub>, 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'' <sub>0</sub> og nul.
 
=== Bevis for korrekthed ===
: {{Math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}}
 
hvor ''r''<sub>''k''</sub> er ikke-negativ og strengt mindre end [[Numerisk værdi|størrelsen]] på ''r'' <sub>''k''−1</sub>. 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.<ref>{{Cite book|title=Abstract Algebra|last=Dummit|first=David S.|last2=Foote|first2=Richard M.|publisher=John Wiley & Sons, Inc.|year=2004|isbn=978-0-471-43334-7|location=|pages=270-271}}</ref>
 
I Euklids originale version af algoritmen findes kvotienten og resten ved gentagen subtraktion; dvs. ''r'' <sub>''k''−1</sub> trækkes fra ''r''<sub>''k''−2</sub>, indtil resten ''r'' <sub>''k''</sub> er mindre end ''r'' <sub>''k''−1</sub> . Derefter byttes der om på ''r'' <sub>''k''</sub> og ''r''<sub>''k''−1</sub> (så ''r''<sub>''k''</sub> næste gang trækkes fra ''r''<sub>''k''−1</sub>), 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 [[modulo]]operationen, der kun giver resten. Således bliver hver iteration af Euklids algoritme simpelthen