✖

Største felles faktor

Største felles faktor av to heltall er det tallet som deler begge tallene uten rest, og der det ikke finnes noe annet, større tall som også deler begge tallene uten rest.

La oss som eksempel ta tallene 24 og 32. Hva er deres største felles faktor? Først leter vi etter et tall som deler begge tallene.

  • For eksempel deler tallet 12 tallet 24, men ikke tallet 32, for 32 / 12 er lik 2,666… som ikke er et heltall. Tallet 12 kan altså ikke være største felles faktor av 24 og 32.
  • Hva med tallet 4? Det deler begge tallene, 24 / 4 er lik 6 og 32 / 4 er lik 8. Tallet 4 er altså vår første kandidat. Finnes det et større tall som deler begge tallene?
  • Tallet 8 deler både 24 og 32 og er samtidig større enn 4.
  • Det finnes ikke noe annet tall større enn 8 som deler begge tallene. Tallet 8 er altså største felles faktor av 24 og 32.

Euklids algoritme for å finne største felles faktor

Det finnes en ganske enkel måte å finne største felles faktor av to tall på, med Euklids algoritme. La oss i begynnelsen ha to tall x og y som vi vil finne største felles faktor for. Som eksempel prøver vi med tallene x = 50 og y = 35. Så går vi fram slik:

  1. Vi deler x / y og husker resten. Denne resten kaller vi z. For eksempelet vårt får vi 50 / 35, som gir resten z = 15.
  2. Nå bytter vi om på variablene: vi lagrer verdien av y i variabelen x og verdien av z i y. Den opprinnelige verdien av x kaster vi. Etter dette trinnet har vi x = 35 og y = 15.
  3. Nå ser vi etter om y er lik null. Hvis den er det, er tallet x største felles faktor. Siden y ikke er lik null, fortsetter vi og gjentar hele fremgangsmåten fra første punkt.
  4. Vi deler igjen x / y, altså 35 / 15, som gir resten z = 5.
  5. Vi bytter om på variablene og får x = 15 og y = 5. Siden y ikke er lik null, fortsetter vi.
  6. Vi deler x / y, altså 15 / 5. Resten er z = 0.
  7. Vi bytter om på variablene og får x = 5 og y = 0.
  8. Nå er y = 0, og algoritmen vår stopper. Største felles faktor er tallet x = 5.

Det er viktig at rekkefølgen på tallene ikke spiller noen rolle. Hvis vi byttet om på tallene i eksempelet, ville vi fått paret x = 35 og y = 50. Fremgangsmåten ville vært den samme:

  1. Vi deler x / y, altså 35 / 50, som gir resten z = 35.
  2. Vi bytter om på variablene: x = 50 og y = 35.
  3. Vi ser at vi etter dette trinnet bare har byttet om innholdet i variablene x og y …

Kalkulator

Denne kalkulatoren regner ut største felles faktor for deg.