✖

Största gemensamma delare

Den största gemensamma delaren (sgd) av två heltal är det tal som delar båda talen utan rest och för vilket det inte finns något större tal som också delar båda talen utan rest.

Som exempel tar vi talen 24 och 32. Vad är deras största gemensamma delare? Först söker vi ett tal som delar båda talen.

  • Talet 12 delar visserligen 24, men det delar inte 32, eftersom 32 / 12 är 2,666… och det är inget heltal. Talet 12 kan alltså inte vara den största gemensamma delaren av 24 och 32.
  • Hur är det med talet 4? Det delar båda talen: 24 / 4 är 6 och 32 / 4 är 8. Talet 4 är alltså vår första kandidat. Finns det något större tal som delar båda talen?
  • Talet 8 delar både 24 och 32 och är dessutom större än 4.
  • Det finns inget annat tal större än 8 som delar båda talen. Talet 8 är alltså den största gemensamma delaren av 24 och 32.

Euklides algoritm för att hitta den största gemensamma delaren

Det finns ett ganska enkelt sätt att hitta den största gemensamma delaren av två tal, nämligen Euklides algoritm. Vi börjar med två tal x och y vars största gemensamma delare vi vill hitta. Som exempel provar vi talen x = 50 och y = 35. Sedan gör vi så här:

  1. Vi dividerar x / y och kommer ihåg resten. Resten kallar vi z. I vårt exempel ger 50 / 35 resten z = 15.
  2. Nu byter vi värden i variablerna: vi lagrar värdet av y i x och värdet av z i y. Det ursprungliga värdet av x kastar vi bort. Efter det här steget har vi x = 35 och y = 15.
  3. Nu tittar vi på om y är lika med noll. Om det är det, är x den största gemensamma delaren. Eftersom y inte är noll fortsätter vi och upprepar hela proceduren från det första steget.
  4. Vi dividerar på nytt x / y, alltså 35 / 15, vilket ger resten z = 5.
  5. Vi byter variablerna och får x = 15 och y = 5. Eftersom y inte är noll fortsätter vi.
  6. Vi dividerar x / y, alltså 15 / 5. Resten är z = 0.
  7. Vi byter variablerna och får x = 5 och y = 0.
  8. Nu är y = 0 och algoritmen tar slut. Den största gemensamma delaren är talet x = 5.

Det viktiga är att ordningen på talen inte spelar någon roll. Om vi byter plats på talen i exemplet får vi paret x = 35 och y = 50. Förloppet blir detsamma:

  1. Vi dividerar x / y, alltså 35 / 50, vilket ger resten z = 35.
  2. Vi byter variablerna: x = 50 och y = 35.
  3. Vi ser att vi efter det här steget bara har bytt innehåll mellan variablerna x och y …

Miniräknare

Den här miniräknaren beräknar den största gemensamma delaren åt dig.