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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Най-големият общ делител на a и b се означава като НОД(ab), GCD(ab) или понякога просто (ab). Например, НОД(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.

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

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

Много по-ефективен е Алгоритъмът на Евклид:

  1) За делимо се взима по-голямото число, а за делител - по-малкото число.
2) Делителя от предишната стъпка се разделя на получения остатък.
3) Това се повтаря дотогава, докато получим остатък 0. Този делител, при който частното няма остатък е НОД.


Използвайки за илюстрация примерът описан по-горе - НОД(18,84) - получаваме:

84 : 18 = 4 и остатък 12
18 : 12 = 1 и остатък 6
12 : 6 = 2 без остатък

=> НОД(18,84) = 6

Свойства[редактиране | edit source]

  • Всеки общ делител на a и b е делител на НОД(ab).
  • НОД(ab), където a или b не е нула, може да се дефинира еквивалентно по друг начин като най-малкото положително цяло число d, което може да се запише във формата d = a·p + b·q, където p и q са цели числа. Този израз се нарича тъждество на Безу. Числата p и q могат да се изчислят чрез разширения алгоритъм на Евклид.
  • Ако a е делител на произведението b·c, и НОД(ab) = d, то a/d е делител на c.
  • За произволно цяло число m НОД(m·am·b) = m·gcd(ab) и НОД(a + m·bb) = gcd(ab). Ако m е ненулев общ делител на a и b, то НОД(a/mb/m) = gcd(ab)/m.
  • НОД на три числа може да се пресметне като НОД(abc) = НОД(НОД(ab), c) = НОД(a, gcd(bc)). Следователно НОД е асоциативна операция.
НОД(ab)·НОК(ab) = a·b.
Тази формула често се използва за пресмятане на общи кратни: първо се изчислява НОД по алгоритъма на Евклид и след това се дели произведението на зададените числа на техния НОД. Валидни са следните варианти на дистрибутивност:
НОД(a, НОК(bc)) = НОК(НОД(ab), НОД(ac))
НОК(a, НОД(bc)) = НОД(НОК(ab), НОК(ac)).
  • Полезно е да се дефинира НОД(0, 0) = 0 и НОК(0, 0) = 0, защото тогава естествените числа стават пълна дистрибутивна решетка с НОД като инфимум и НОК като супремум операция. Това разширение на дефиницията е съвместимо и с обобщението за комутативни пръстени, дадено по-долу.

НОД в комутативни пръстени[редактиране | edit source]

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

Ако 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 е евклидова област, то за изчисляване на най-големите общи делители може да се използва една форма на алгоритъма на евклид.

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

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 нямат най-голям общ делител. (Ернст Кумер използва този идеал като заместител на НОД в работата си върху последната теорема на Ферма)

Вижте също[редактиране | edit source]