Lielākais kopīgais dalītājs

Matemātikā par divu vai vairāk veselu skaitļu lielāko kopīgo dalītāju sauc lielāko naturālo skaitli, ar kuru katrs no dotajiem skaitļiem dalās bez atlikuma. Piemēram, skaitļu 12 un 30 lielākais kopīgais dalītājs ir LKD(12, 30) = 6, jo gan 12, gan 30 dalās ar 6, bet nav neviena lielāka naturāla skaitļa, ar kuru tie abi dalītos. Lielākais kopīgais dalītājs nav definēts skaitļiem, kuri visi ir vienādi ar 0.

Efektīvs algoritms divu skaitļu lielākā kopīgā dalītāja aprēķināšanai ir Eiklīda algoritms.
Lielākā kopīgā dalītāja jēdzienu var attiecināt arī uz polinomiem.

Apzīmējumi un terminoloģija

Literatūrā, kas ir latviešu valodā, skaitļu a un b lielāko kopīgo dalītāju parasti apzīmē ar LKD(a, b) vai retāk ar ld(a, b). Angļu valodā visbiežāk ir sastopams apzīmējums gcd(a, b), kas ir saīsinājums no greatest common divisor. Reizēm lieto saīsinātu apzīmējumu (a, b).

Divus skaitļus, kuru lielākais kopīgais dalītājs ir 1, sauc par savstarpējiem pirmskaitļiem. Piemēram, LKD(5, 14) = 1, tāpēc 5 un 14 ir savstarpēji pirmskaitļi.

Īpašības

Operācijai LKD piemīt šādas īpašības (šeit a, b, c un m ir naturāli skaitļi):

• LKD(a, a) = a (idempotence).
• LKD(a, 1) = 1 (jebkurš naturāls skaitlis ir savstarpējs pirmskaitlis ar skaitli 1).
• LKD(a, b) = LKD(b, a) (komutativitāte).
• LKD(a, a + 1) = 1 (secīgi naturāli skaitļi ir savstarpēji pirmskaitļi).
• LKD(a, LKD(b, c)) = LKD(LKD(a, b), c) = LKD(a, b, c) (asociativitāte).
• LKD(m · a, m · b) = m · LKD(a, b) (multiplikativitāte).
• Ja a un b dalās ar m, tad LKD(a, b) arī dalās ar m, pie kam LKD(a/m, b/m) = LKD(a, b) / m.
• LKD(a^m, b^m) = LKD(a, b)^m.

Pielietojumi

Lielāko kopīgo dalītāju ir nepieciešams atrast, lai saīsinātu daļskaitļus. Piemēram, lai saīsinātu daļskaitli 12/16, aprēķina LKD(12, 16) = 4 un veic saīsināšanu ar 4:

${\frac {12}{16}}={\frac {12/4}{16/4}}={\frac {3}{4}}.$

To lieto arī lai vienkāršotu dažādas algebriskas izteiksmes, piemēram:

${\sqrt[{6}]{x^{3}}}=x^{\frac {3}{6}}=x^{\frac {1}{2}}={\sqrt {x}}$.

Skatīt arī

• Dalītājs
• Mazākais kopīgais dalāmais
• Eiklīda algoritms
• Paplašinātais Eiklīda algoritms

Ārējās saites

• Eric W. Weisstein, Greatest Common Divisor, MathWorld.