Euklids algoritme

Dette innlegget har allerede blitt vist 1559 ganger!

Euklids algoritme brukes for å beregne største felles divisor til to tall. Dette er en enkel teknikk som er veldig effektiv, også med relativt store tall. Hele ideen er basert på at man kan bytte ut tallene med mindre tall slik at det blir lettere å regne.

Teorem: La a og b være naturlige tall.

  • Hvis b a, så er gcd(a, b) = b
  • gcd(a,b) = gcd(b, a mod b)

Eksempel:

Regn ut gcd(321,78):
gcd(321,78) = gcd(78, 321 mod 78) = gcd(78,9)
gcd(78,9) = gcd(9, 78 mod 9) = gcd(9, 6)
gcd(9,6) = gcd(6, 9 mod 6) = gcd(6, 3)
siden 3 6 er gcd(6,3) = 3.
gcd(321,78) = gcd(6,3) = 3

For å slippe mye gjentagende tekst bruker man som oftest en annen syntaks når man regner ut største felles divisor ved hjelp av Euklids algoritme. Denne viser seg å også være veldig nyttig når man skal se på Lineære diofantiske likninger.

Regn ut gcd(321,78):
321 = 4×78 + 9
78 = 8×9 + 6
9 = 1×6 + 3
6 = 2×3 + 0
Altså gcd(321,78) = gcd(78,9) = gcd(9,6) = gcd(6,3) = 3