Euklids algoritme for største felles faktor

Euklids algoritme for å finne største felles faktor kan enkelt beskrives slik:

Start med de to tallene du skal finne største felles faktor for.
Erstatt det største tallet med differansen mellom det største og det minste.
Gjenta dette til de to tallene er like store. Da har du funnet største felles faktor.

Eksempel:
Største felles faktor til 26 og 44:
Erstatter 44 med 44-26 = 18 og står igjen med 26 og 18
Erstatter 26 med 26-18 = 8 og står igjen med 18 og 8
Erstatter 18 med 18-8 = 10 og står igjen med 10 og 6
Erstatter 10 med 10-6 = 4 og står igjen med 4 og 6.
Erstatter 6 med 6-4 = 2 og står igjen med 4 og 2.
Erstatter 4 med 4-2 = 2 og står igjen med 2 og 2.
Altså er 2 største felles faktor til 26 og 44.

Algoritmen kan effektiviseres ved å bruke divisjon istedenfor å trekke fra det samme tallet gjentatte ganger.

Se epsilon s. 139-141 for mer om Euklids algoritme.

Euklids algoritme er sentral for løsning av Diofantiske likninger.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License