Den største fælles divisor, eller GCD, er det største tal, der divisorer to eller flere hele tal uden en rest. For 12 og 18 er divisorerne 1, 2, 3, 6 for begge, så GCD er 6. GCD kaldes også den største fælles divisor.

Euclids algoritme finder GCD effektivt. Divider det større med det mindre, erstat derefter det større med resten, og gentag indtil resten er nul. Den sidste rest, der ikke er nul, er GCD. Metoden er over to tusind år gammel og bruges stadig i datalogi.

GCD forenkler brøker. Ved at dividere tæller og nævner med deres GCD reduceres en brøk til de laveste led. Den forekommer også i modular aritmetik, kryptografi og talteori. Det mindste fælles multiplum relaterer sig til GCD ved formlen LCM(a, b) = a × b / GCD(a, b).

• Største tal dividerer heltal præcist
• Fundet af Euclids algoritme
• Bruges til at forenkle brøker
• Relaterer sig til LCM ved hjælp af en simpel formel