Største felles divisor

Største felles divisor (forkortet SFD eller sff, 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

gcd-kalkulator