|
'''Най-голям общ делител''' (НОД) на две [[цяло число|цели числа]], поне едното от които е различно от нула, в [[математика]]та е най-голямото цяло число, което [[Деление|дели]] и двете числа без остатък.
Най-големият общ делител на ''a'' и ''b'' се означава като НОД(''a'', ''b''), GCD(''a'', ''b'') или понякога просто (''a'', ''b''). Например НОД(12, 18) = 6, НОД(−4, 14) = 2 и НОД(5, 0) = 5. Две числа се наричат „[[взаимно прости числа|взаимно прости]]“, ако техният най-голям общ делител е 1, т.е. нямат общ [[делител]], различен от 1. Например 9 и 28 са взаимно прости.
Най-големият общ делител е полезен при съкращаването на обикновени [[дроби]]. Например в
По принцип най-големите общи делители могат да се пресметнат, като се разложат двете числа на [[просто число|прости]] множители (т.нар. [[факторизация]]) и се сравнят множителите.
Например: за да се изчисли НОД(18, 84), се разлагат числата на прости множители 18 = 2×3<sup>2</sup> и 84 = 2<sup>2</sup>×3×7 и се установява, че сечението е 2×3. Следователно НОД(18,84) = 6.
Много по-ефективен е [[Алгоритъм на Евклид|алгоритъмът на Евклид]]:
== Свойства ==
* Всеки общ делител на ''a'' и ''b'' е делител на НОД(''a'', ''b'').
* НОД(''a'', ''b''), където ''a'' или ''b'' не е нула, може да се дефинира еквивалентно по друг начин като най-малкото положително цяло число ''d'', което може да се запише във формата: ''d'' = ''a''·''p'' + ''b''·''q'', където ''p'' и ''q'' са цели числа. Този израз се нарича [[тъждество на Безу]]. Числата ''p'' и ''q'' могат да се изчислят чрез [[Разширен алгоритъм на Евклид|разширения алгоритъм на Евклид]].
* Ако ''a'' е делител на произведението ''b''·''c'', и НОД(''a'', ''b'') = ''d'', то ''a''/''d'' е делител на ''c''.
* За произволно цяло число ''m'' НОД(''m''·''a'', ''m''·''b'') = ''m''·gcd(''a'', ''b'') и НОД(''a'' + ''m''·''b'', ''b'') = gcd(''a'', ''b''). Ако ''m'' е ненулев общ делител на ''a'' и ''b'', то НОД(''a''/''m'', ''b''/''m'') = gcd(''a'', ''b'')/''m''.
* НОД е [[мултипликативна функция]] в следния смисъл: ако ''a''<sub>1</sub> и ''a''<sub>2</sub> са взаимно прости, то НОД(''a''<sub>1</sub>·''a''<sub>2</sub>, ''b'') = НОД(''a''<sub>1</sub>, ''b'')·НОД(''a''<sub>2</sub>, ''b'').
* НОД на три числа може да се пресметне като НОД(''a'', ''b'', ''c'') = НОД(НОД(''a'', ''b''), ''c'') = НОД(''a'', gcd(''b'', ''c'')). Следователно НОД е [[асоциативност|асоциативна]] операция.
* НОД(''a'', ''b'') е тясно свързано с [[най-малко общо кратно|най-малкото общо кратно]] НОК(''a'', ''b''): в сила е
::НОД(''a'', ''b'')·НОК(''a'', ''b'') = ''a''·''b''.
:Тази формула често се използва за пресмятане на общи кратни: първо се изчислява НОД по алгоритъма на Евклид и след това се дели произведението на зададените числа на техния НОД. Валидни са следните варианти на [[дистрибутивност]]:
::НОД(''a'', НОК(''b'', ''c'')) = НОК(НОД(''a'', ''b''), НОД(''a'', ''c''))
::НОК(''a'', НОД(''b'', ''c'')) = НОД(НОК(''a'', ''b''), НОК(''a'', ''c'')).
* Полезно е да се дефинира НОД(0, 0) = 0 и НОК(0, 0) = 0, защото тогава [[естествено число|естествените числа]] стават [[пълна решетка|пълна]] [[дистрибутивна решетка|дистрибутивна]] [[решетка (теория на множествата)|решетка]] с НОД като инфимум и НОК като супремум операция. Това разширение на дефиницията е съвместимо и с обобщението за комутативни пръстени, дадено по-долу.
* В [[декартова координатна система]] НОК(''a'', ''b'') може да се интерпретира като броя точки с цели координати върху [[отсечка]]та, свързваща началото(0, 0) и (''a'', ''b''), без (0, 0).
== НОД в комутативни пръстени ==
Най-големият общ делител може да се дефинира по-обобщено за елементите на произволен [[комутативен пръстен]].
Ако ''R'' е комутативен пръстен и ''a'' и ''b'' са в ''R'', то един елемент ''d'' на ''R'' се елементи ''x'' и ''y'' в ''R'' такива, че ''d''·''x'' = ''a'' и ''d''·''y'' = ''b''). Ако ''d'' е общ делител на ''a'' и ''b'' и всеки общ делител на ''a'' и ''b'' е делител на ''d'', то ''d'' се нарича ''най-голям общ делител'' на ''a'' и ''b''.
Зебележете, че с тази дефиниция двата елемента ''a'' и ''b'' могат да имат няколко най-големи общи делителя или въобще да нямат такива. Но ако ''R'' е [[област на цялостност]], то всеки два НОД на ''a'' и ''b'' трябва да са свързани елементи. Също така, ако ''R'' е [[факториален пръстен]], то всеки два елемента имат НОД. Ако ''R'' е [[евклидова област]], то за изчисляване на най-големите общи делители може да се използва една форма на алгоритъма на евклид.
| 