Største fælles divisor

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg
Matematik Stub
Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.

Største fælles divisor (eng. greatest common divisor) for to naturlige tal m og n, er det største naturlige tal d, som er divisor i både m og n. Notationen for den største fælles divisor, af for eksempel m og n, er sfd(m,n) = d, men ofte bruges også den engelske notation: gcd(m,n) = d.

Den største fælles divisor finder anvendelse, når en forkortelig brøk skal reduceres, idet den største fælles divisor af tæller og nævner kan bruges til at forkorte brøken mest muligt.

En klassisk effektiv algoritme til at bestemme den største fælles divisor, kaldet Euklids algoritme, blev fundet af den græske matematiker Euklid (ca. 325 f.Kr.-ca. 270 f.Kr.).

Se også[redigér | redigér wikikode]