Euklids algoritme

**Euklids algoritme** er en fremgangsmåte for å beregne på en systematisk måte den største felles divisor til to elementer som tilhører en euklidsk ring.  I det enkleste tilfelle benyttes den for heltall. Algoritmen er en av de eldste som er kjent og har fått sitt navn etter den greske matematiker Euklid. Han beskrev den i sitt hovedverk *[[Elementer]]* som kan dateres tilbake til antikkens Hellas. Den samme fremgangsmåten kan også benyttes til å forenkle generelle brøker og har mange anvendelser i moderne tallteori.

## 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 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.

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, og man vil generelt ikke finne noe noe heltallig svar.

### Fremgangsmåte

Først måler man hvor mange hele ganger *q*0 som *b* kan plasseres langs *a*. Generelt vil det da oppstå en rest *r*0  a = q_0 b + r_0 

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

:  b = q_1 r_0 + r_1 

hvor nå  *r*1 0. På denne måten fortsetter man og måler hvor mange ganger *r*1 er inneholdt i *r*0,

:  r_0  = q_2 r_1 + r_2 

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

:  r_{n-1}  = q_{n+1} r_n + r_{n+1} 

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 , vil man ha at . Innsatt i den forrige ligningen, har man da . Herav kan så *r*0 bestemmes uttrykt ved lengden *b*. Resultatet er da kjedebrøken  som utskrevet er

: {a\over b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3}}} 

I prinsippet gir denne fremgangsmåten et resultat som kan bli så nøyaktig som man ønsker ved å foreta disse gjentagelsene lenge nok.

## Største felles faktor

Den samme algoritmen kan også bli benyttet til å finne største felles faktor av to tall *a* og *b*. Hvis man etter *n* stepp finner at resten *r**n*+1 = 0, vil denne felles faktor være den foregående resten *r**n*. De to tallene sies da å være kommensurable.

Som et konkret eksempel kan man betrakte tallene *a* = 551551 og *b* = 50065. Da får man videre fra algoritmen

: \begin{align} 551551 &= 50065 \times 11 + 836 \\ 50065 &= 836 \times 59 + 741\\  836 &= 741 \times 1 + 95\\  741 &= 95 \times 7 + 76\\ 95 &= 76 \times 1 + 19 \\ 76 &= 19\times 4 + 0 \end{align} 

Største felles faktor for 551551 og 50065 er derfor 19.

### Dataprogram

Algoritmen til Euklid er rekursiv og kan derfor lett implementeres på en elektronisk datamaskin. Man kan da definere en funksjon SFD(*a,b*) som gir største felles divisor av de to heltallene *a* og *b*. Strukturen til programmet vil da være

 **funksjon** SFD(a, b)
      **hvis** b = 0 **returner** a
      **ellers** **returner** SFD(b, a **mod** b)

Her benyttes den innebygde modulo-funksjonen **mod** som gir resten etter en heltallsdivisjon.

I  programmeringsspråkene C++ eller  Java vil algoritmen se ut som

  int SFD(int a,int b){
    if ( b == 0 )
      return a;
    return SFD(b,a%b);
  }

hvor modulo-funksjonen betegnes med prosentsymbolet %.

## Faktorisering av polynom

Polynom kan adderes og multipliseres sammen. De kan på den måten danne en matematisk ring med tilsvarende egenskaper som heltallene **Z**. Av den grunn kan et polynom ofte faktoriseres i et produkt av et eller flere andre polynom av lavere grad. Denne faktorisering kan også systematisk utføres ved hjelp av Euklids algoritme.

Hvis man er gitt ett polynom *a*(*x*) og et annet *b*(*x*) av samme eller lavere grad, kan man alltid foreta en oppsplitting av formen

:  a(x) = q(x)b(x) + r(x) 

hvor de to polynomene *q*(*x*) og *r*(*x*)  entydig kan bestemmes. Polynomet *b*(*x*) kan så splittes opp på en tilsvarende måte og dermed gi opphav til et nytt restpolynom *r*(*x*) . Denne prosessen fortsettes så til man står igjen med et restpolynom som er null. Den største felles faktor av polynomene *a*(*x*) og *b*(*x*) er da det foregående restpolynomet.

Fremgangsmåten kan illustreres ved et enkelt eksempel der 

:  a(x) = x^3 - 4x^2 - 3x + 18, \;\;\; b(x) = x^2 - 2x - 8 

Da er

: \begin{align} a(x) &=  (x^2 - 2x - 8)(x - 2) + x + 2\\ b(x) &= (x - 4)(x + 2) + 0 \end{align}  ,

slik at den felles faktor er  x + 2 . Polynomet  *a*(*x*) kan derfor splittes opp og man finner

:  x^3 - 4x^2 - 3x + 18 = (x + 2)(x - 3)^2 

Det er først når de gitte polynomene har mye høyere grad, at denne algoritmen virkelig kommer til sin fulle bruk.

## Se også

* Kjedebrøk
* Største felles faktor

## Referanser


## Eksterne lenker

* J. O'Connor and E. Robertson, ''Division and Euclidean algorithms'' , University of St. Andrews, Scotland