Største felles divisor

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Største felles divisor (forkortet SFD[1] eller sff[trenger referanse], engelsk forkortelse: gcd, greatest common divisor), også benevnt Største felles faktor og største felles nevner, til to tall, er det største tallet som deler begge tallene. Største felles faktor til to tall, a og b, betegnes ofte med gcd(a,b) eller ganske enkelt (a,b). Hvis a og b ikke har felles faktorer, det vil si at (a,b) = 1, sier vi at a og b er relativt primiske.

For å beregne største felles faktor, går det an å bruke euklids algoritme som finner et svar på O(log(maks(a,b)) tid.

For eksempel er (15,50) = 5, da 5 er det største hele tallet som deler 15 og 50 uten rest. På denne måten er det også lett å forkorte brøker, da vi har at \frac{15}{50}=\frac{5*3}{5*10}=\frac{3}{10}

Største felles faktor henger også sammen med minste felles multiplum (lcm), da lcm(a,b)=a*b/(a,b).

Eksterne lenker[rediger | rediger kilde]

gcd-kalkulator

Referanser[rediger | rediger kilde]

  1. ^ Matematikkleksikon 2006, s.110