✖

Største fælles divisor

Den største fælles divisor af to hele tal er det tal, som går op i begge tal uden rest, og hvor der samtidig ikke findes noget andet, større tal, som også går op i begge tal uden rest.

Lad os som eksempel tage tallene 24 og 32. Hvad er deres største fælles divisor? Først og fremmest leder vi efter et tal, som går op i begge tal.

  • For eksempel går tallet 12 op i tallet 24, men ikke i tallet 32, for 32 / 12 er lig med 2,666…, og det er ikke et helt tal. Så tallet 12 kan ikke være den største fælles divisor af tallene 24 og 32.
  • Hvad så med tallet 4? Det går op i begge tal, 24 / 4 er lig med 6 og 32 / 4 er lig med 8. Tallet 4 er altså vores første kandidat. Findes der et større tal, som går op i begge tal?
  • Tallet 8 går op i både tallet 24 og tallet 32, og det er samtidig større end tallet 4.
  • Der findes intet andet tal større end 8, som går op i begge tal. Tallet 8 er altså den største fælles divisor af tallene 24 og 32.

Euklids algoritme til at finde den største fælles divisor

Der findes en forholdsvis enkel måde at finde den største fælles divisor af to tal på med Euklids algoritme. Lad os starte med to tal x og y, som vi vil finde den største fælles divisor af. Som eksempel prøver vi det med tallene x = 50 og y = 35. Så går vi frem på følgende måde:

  1. Vi dividerer x / y og husker resten. Denne rest betegner vi z. For vores eksempel får vi 50 / 35, som giver resten z = 15.
  2. Nu bytter vi om på variablerne, så vi gemmer værdien af y i variablen x og værdien af z i y. Den oprindelige værdi af x smider vi væk. Efter dette trin har vi x = 35 og y = 15.
  3. Nu ser vi efter, om y er lig med nul. Hvis det er tilfældet, er den største fælles divisor tallet x. Fordi y ikke er lig med nul, fortsætter vi og gentager hele fremgangsmåden fra første punkt.
  4. Vi dividerer igen x / y, altså 35 / 15, som giver resten z = 5.
  5. Vi bytter om på variablerne, så vi får x = 15 og y = 5. Fordi y ikke er lig med nul, fortsætter vi.
  6. Vi dividerer x / y, altså 15 / 5. Resten er z = 0.
  7. Vi bytter om på variablerne og får x = 5 og y = 0.
  8. Nu er y = 0, og vores algoritme slutter. Den største fælles divisor er tallet x = 5.

Det er vigtigt, at rækkefølgen af tallene er ligegyldig. Hvis vi byttede om på tallene i eksemplet, ville vi få parret x = 35 og y = 50. Fremgangsmåden ville være den samme:

  1. Vi dividerer x / y, altså 35 / 50, som giver resten z = 35.
  2. Vi bytter om på variablerne x = 50 og y = 35.
  3. Vi ser, at vi efter dette trin bare har byttet om på indholdet af variablerne x og y…

Beregner

Denne beregner finder den største fælles divisor for dig.