Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних чисел — найбільше натуральне число, на яке ці числа діляться без остачі.
Огляд
Позначення
Найбільший спільний дільник двох чисел a і b позначається як НСД(a, b), деколи (a, b). В англомовній літературі прийнято вживати позначення gcd(a, b).
Приклад
Число 54 може бути виражене як добуток двох інших цілих чисел кількома способами:
Отже дільниками числа 54 є:
Аналогічно дільниками числа 24 є:
Числа, які знаходяться в обох цих списках, є спільними дільниками чисел 54 та 24:
Найбільшим серед них є число 6. Воно є найбільшим спільним дільником чисел 54 та 24. Можна записати:
Скорочення дробів
Найбільший спільний дільник використовується для скорочення дробів. Наприклад, НСД(42, 56) = 14, тому,
Властивості
- НСД є комутативною функцією: НСД(a, b)= НСД(b, a).
- НСД(a, b)
- НСД(a, b, c, d) = НСД(НСД(a, b), НСД(c, d))
- НСД(a, b) =|ab|/НСК(a, b), де НСК(a, b) найменше спільне кратне чисел a, b.
Обчислення НСД методом розкладу на прості множники
Нехай розклад чисел на прості множники має вигляд:
Тоді
- НСД
Приклад
Визначимо НСД. Розклад на прості множники:
- ,
або, подаючи для наочності нульові степені,
- ,
Отже,
- НСД
Ефективним алгоритмом обчислення НСД є алгоритм Евкліда
НСД в кільці многочленів
В кільці многочленів над довільним полем найбільшим спільним дільником многочленів і , принаймні один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени і Обчислити НСД можна (розкладаючи многочлен на нескоротні множники). Можна застосувати також алгоритм Евкліда.
Приклад
Обчислимо НСД двох многочленів над полем дійсних чисел:
Розкладаючи многочлени на нескоротні множники
- ,
отримуємо
НСД .
Приклади програмної реалізації знаходження НСД
Рекурсивна реалізація:
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
Реалізація без використання рекурсії:
int gcd(int a, int b) { if (a == 0) return b; while (b != 0) { if( a > b ){ int r = a % b; } else { int r = b % a; } a = b; b = r; } return a; }
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Najbi lshij spi lnij dilni k NSD dvoh abo bilshe nevid yemnih chisel najbilshe naturalne chislo na yake ci chisla dilyatsya bez ostachi OglyadPoznachennya Najbilshij spilnij dilnik dvoh chisel a i b poznachayetsya yak NSD a b dekoli a b V anglomovnij literaturi prijnyato vzhivati poznachennya gcd a b Priklad Chislo 54 mozhe buti virazhene yak dobutok dvoh inshih cilih chisel kilkoma sposobami 54 1 27 2 18 3 9 6 displaystyle 54 times 1 27 times 2 18 times 3 9 times 6 Otzhe dilnikami chisla 54 ye 1 2 3 6 9 18 27 54 displaystyle 1 2 3 6 9 18 27 54 Analogichno dilnikami chisla 24 ye 24 1 12 2 8 3 6 4 displaystyle 24 times 1 12 times 2 8 times 3 6 times 4 1 2 3 4 6 8 12 24 displaystyle 1 2 3 4 6 8 12 24 Chisla yaki znahodyatsya v oboh cih spiskah ye spilnimi dilnikami chisel 54 ta 24 1 2 3 6 displaystyle 1 2 3 6 Najbilshim sered nih ye chislo 6 Vono ye najbilshim spilnim dilnikom chisel 54 ta 24 Mozhna zapisati 54 24 6 displaystyle 54 24 6 Skorochennya drobiv Najbilshij spilnij dilnik vikoristovuyetsya dlya skorochennya drobiv Napriklad NSD 42 56 14 tomu 4256 3 144 14 34 displaystyle 42 over 56 3 cdot 14 over 4 cdot 14 3 over 4 VlastivostiNSD ye komutativnoyu funkciyeyu NSD a b NSD b a 1 displaystyle 1 leq NSD a b min a b displaystyle leq min a b NSD a b c d NSD NSD a b NSD c d NSD a b ab NSK a b de NSK a b najmenshe spilne kratne chisel a b Obchislennya NSD metodom rozkladu na prosti mnozhnikiNehaj rozklad chisel na prosti mnozhniki maye viglyad a 2q2 3q3 pkqpk displaystyle a 2 q 2 cdot 3 q 3 cdot dots cdot p k q p k b 2r2 3r3 pkrpk displaystyle b 2 r 2 cdot 3 r 3 cdot dots cdot p k r p k Todi NSD a b 2min q2 r2 3min q3 r3 pkmin qpk qpk displaystyle a b 2 min q 2 r 2 cdot 3 min q 3 r 3 cdot dots cdot p k min q p k q p k Priklad Viznachimo NSD 840 396 displaystyle 840 396 Rozklad na prosti mnozhniki 840 23 3 5 7 displaystyle 840 2 3 cdot 3 cdot 5 cdot 7 396 22 32 11 displaystyle 396 2 2 cdot 3 2 cdot 11 abo podayuchi dlya naochnosti nulovi stepeni 840 23 31 51 71 110 displaystyle 840 2 3 cdot 3 1 cdot 5 1 cdot 7 1 cdot 11 0 396 22 32 50 70 111 displaystyle 396 2 2 cdot 3 2 cdot 5 0 cdot 7 0 cdot 11 1 Otzhe NSD 840 396 22 31 50 70 110 12 displaystyle 840 396 2 2 cdot 3 1 cdot 5 0 cdot 7 0 cdot 11 0 12 Efektivnim algoritmom obchislennya NSD ye algoritm EvklidaNSD v kilci mnogochlenivV kilci mnogochleniv K X displaystyle K X nad dovilnim polem K displaystyle K najbilshim spilnim dilnikom mnogochleniv f x displaystyle f x i g x displaystyle g x prinajmni odin z yakih ye vidminnij vid nulya nazivayemo normovanij mnogochlen najvishogo stepenya yakij dilit obidva mnogochleni f x displaystyle f x i g x displaystyle g x Obchisliti NSD mozhna rozkladayuchi mnogochlen na neskorotni mnozhniki Mozhna zastosuvati takozh algoritm Evklida Priklad Obchislimo NSD dvoh mnogochleniv nad polem dijsnih chisel f x 2x3 6x2 14x 10 displaystyle f x 2x 3 6x 2 14x 10 g x 3x2 3x 6 displaystyle g x 3x 2 3x 6 Rozkladayuchi mnogochleni na neskorotni mnozhniki f x 2 x 1 x2 2x 5 displaystyle f x 2 x 1 x 2 2x 5 g x 3 x 1 x 2 displaystyle g x 3 x 1 x 2 otrimuyemo NSD f x g x x 1 displaystyle f x g x x 1 Prikladi programnoyi realizaciyi znahodzhennya NSDRekursivna realizaciya int gcd int a int b if b 0 return a return gcd b a b Realizaciya bez vikoristannya rekursiyi int gcd int a int b if a 0 return b while b 0 if a gt b int r a b else int r b a a b b r return a Div takozhAlgoritm Evklida Najmenshe spilne kratne