Største fælles divisor

Fra Wikipedia, den frie encyklopædi

Største fælles divisor (eng. greatest common divisor) for to naturlige tal m og n (forkortes sfd), er et naturligt tal d, som både går op i tallene m og n, uden rest. Som bekendt siges et tal d at være en divisor i n, hvis der eksister et heltal q således at n = q*d. Tallet 1 er derfor divisor for ethvert tal. De naturlige tal n forskellig fra 0 har endelig mange divisorer, hvor tallet 0 har uendelig mange divisorer, da ethvert tal er divisor i 0. Tallene m og n har derfor mindst en fælles divisor (nemlig 1) og hvis m er forskellig fra 0 eller n er forskellig fra 0, så må antallet af fælles divisorer for m og n være endelige, hvor den støreste blandt disse oplagt kaldes for den største fælles divisor.

Euklids algoritme er en klassisk effektiv algoritme til at finde den støreste fælles divisor for to naturlige tal.