Alle fag › Diskret matematikk › Største felles divisor

Største felles divisor

Største felles divisor er det største tallet som deler to heltall. Euklids algoritme finner den raskt ved å dele gjentatte ganger og bytte ut tallene med resten, til resten blir null. Den siste resten som ikke er null, er svaret.

gcd⁡(a,b)=gcd⁡(b, a mod b)\gcd(a, b) = \gcd(b,\ a \bmod b)Euklids algoritme
lcm(a,b)=a bgcd⁡(a,b)\text{lcm}(a,b) = \frac{a\,b}{\gcd(a,b)}minste felles multiplum

Symboler

gcd⁡\gcdstørste felles divisor
lcm\text{lcm}minste felles multiplum

Eksempel

gcd⁡(84,36)\gcd(84, 36): 84 mod 36=1284 \bmod 36 = 12 og 36 mod 12=036 \bmod 12 = 0.

Svaret er 12.

Algoritmen er rask selv for store tall, fordi tallene minst halveres annenhver runde.
Øv på grafer og modulregning gratis →

← Modulregning

Del av Diskret matematikk: Grafer og modulregning.