Redigerer Euklids algoritme (avsnitt)

==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''<sub>''n''+1</sub> = 0, vil denne felles faktor være den foregående resten ''r''<sub>''n''</sub>. De to tallene sies da å være [[Kommensurablitet (matematikk)|kommensurable]].<ref name = Ore/>

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

: <math>\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} </math>

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

===Dataprogram===

Algoritmen til Euklid er [[rekursjon|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åk]]ene [[C++]] eller  [[Java (programmeringsspråk)|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 %.