Най-голям общ делител

от Уикипедия, свободната енциклопедия

Най-голям общ делител (НОД) на две цели числа, поне едното от които е различно от нула, в математиката е най-голямото цяло число, което дели и двете числа без остатък.

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

Най-големият общ делител е полезен при съкращаването на обикновени дроби. Например в

${42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}$

съкратихме 14, най-голям общ делител на 42 и 56.

[редактиране] Изчисляване на НОД

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

Алгоритъмът на Евклид е много по-ефективен метод: разделя се целочислено 84 на 18 и се получава частно 4 и остатък 12. След това се разделя 18 на остатъка 12 и се получава частно 1 и остатък 6. След това се дели 12 на 6 и се пулучава остатък 0, което означава, че НОД е 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₁ и a₂ са взаимно прости, то НОД(a₁·a₂, b) = НОД(a₁, b)·НОД(a₂, 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 се нарича общ делител на a и b, ако е делител и на a, и на b (т.е., ако има елементи 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 е евклидова област, то за изчисляване на най-големите общи делители може да се използва една форма на алгоритъма на евклид.

Ето един пример за област на цялостност с два елемента, които нямат НОД:

$R = \mathbb{Z}[\sqrt{-3}],\quad a = 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}),\quad b = (1+\sqrt{-3})\cdot 2$

Елементите $1+\sqrt{-3}$ и 2 са два „максимални общи делители“ (т.е. всеки общ делител, който е кратен на 2 е свързан с 2, което важи и за $1+\sqrt{-3}$ ), но те не са свързани, така че a и b нямат най-голям общ делител.

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