Преглед на кода на Най-голям общ делител

'''Най-голям общ делител''' (НОД) на две [[цяло число|цели числа]], поне едното от които е различно от нула, в [[математика]]та е най-голямото цяло число, което [[Деление|дели]] и двете числа без остатък. Формалното алгебрично определение, носещо същия смисъл е: „Естественото число ''d'' e е най-голям общ делител на числата ''a'' и ''b'', ако 
# ''d'' дели ''a'' и ''d'' дели ''b''
# от това, че d<sub>1</sub> дели a и ''d''<sub>1</sub> дели ''b'' следва, че ''d''<sub>1</sub> дели ''d'' <ref>{{cite book
 | last = Сидеров
 | first = Пламен
 | title = Теория на числата за ученици
 | url = http://www.wedi.bg
 | year = 2015
 | publisher = Издателство „Веди“
 | location = България
 | isbn = 978-954-8857-37-6
 | pages = 12
}}</ref>

Най-големият общ делител на ''a'' и ''b'' се означава като НОД(''a'', ''b''), GCD(''a'', ''b'') или понякога просто (''a'', ''b''). Например НОД(12, 18) = 6, НОД(−4, 14) = 2 и НОД(5, 0) = 5. Две числа се наричат „[[взаимно прости числа|взаимно прости]]“, ако техният най-голям общ делител е 1, т.е. нямат общ [[делител]], различен от 1. Например 9 и 28 са взаимно прости.

Най-големият общ делител е полезен при съкращаването на обикновени [[дроби]]. Например в
:<math>{42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}</math>
съкратихме 14, най-голям общ делител на 42 и 56.

== Изчисляване на НОД ==
Най-голям общ делител се намира, като се разложат две (или повече) числа на [[просто число|прости]] делители (т.нар. [[факторизация]]) и след това се умножат общите им делители.

Пример: за да се изчисли НОД(18, 84), се разлагат числата на прости множители 18 = 2×3×3 и 84 = 2×2×3×7 и се установява, че общите от тях са 2 и 3. Следователно НОД(18,84) = 2×3 = 6.

Много по-ефективен е [[Алгоритъм на Евклид|алгоритъмът на Евклид]]:
# За делимо се взима по-голямото число, а за делител – по-малкото число.
# Делителят от предишната стъпка се разделя на получения остатък.
# Това се повтаря дотогава, докато получим остатък 0.

Този делител, при който частното няма остатък, е НОД.
{{Br}}
Използвайки за илюстрация примерът описан по-горе – НОД(18,84) – получаваме:
: 84/18 = 4 и остатък 12
: 18/12 = 1 и остатък 6
: 12/6 = 2 без остатък

=> НОД(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'' е [[евклидова област]], то за изчисляване на най-големите общи делители може да се използва една форма на алгоритъма на евклид.

Ето един пример за област на цялостност с два елемента, които нямат НОД:
:<math>R = \mathbb{Z}[\sqrt{-3}],\quad a = 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}),\quad b = (1+\sqrt{-3})\cdot 2</math>
Елементите <math>1+\sqrt{-3}</math> и 2 са два „максимални общи делители“ (т.е. всеки общ делител, който е кратен на 2 е свързан с 2, което важи и за <math>1+\sqrt{-3}</math>), но те не са свързани, така че ''a'' и ''b'' нямат най-голям общ делител.

В съответствие със свойството на Безу във всеки комутативен пръстен може да се разгледа наборът от елементи от вида <math>p a + q b</math>, където ''p'' и ''q'' заемат стойности от пръстена. Това е [[идеал (теория на пръстените)|идеалът]], породен от ''a'' и ''b'' и се означава просто <math>(a,b)</math>. В един пръстен, всички идеали на който са главни ([[област на главните идеали]]), този идеал съвпада с множеството от кратните на някой елемент от пръстена ''d''. Тогава това ''d'' е най-голеям общ делител ''a'' и ''b''. Но идеалът <math>(a,b)</math> може да се използва дори когато ''a'' и ''b'' нямат най-голям общ делител. ([[Ернст Кумер]] използва този идеал като заместител на НОД в работата си върху [[Последна теорема на Ферма|последната теорема на Ферма]])

== Вижте също ==
* [[Най-малко общо кратно]]
* [[Най-малък общ знаменател]]
* [[Двоичен алгоритъм за НОД]]

== Източници ==
{{Reflist}}

[[Категория:Алгебра]]
[[Категория:Теория на числата]]