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

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

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

  1. d дели a и d дели b
  2. от това, че d1 дели a и d1 дели b следва, че d1 дели d [1]

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

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

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

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

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

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

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

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

Този делител, при който частното няма остатък, е НОД.
Използвайки за илюстрация примерът описан по-горе – НОД(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, b, c) = НОД(НОД(a, b), c) = НОД(a, gcd(b, c)). Следователно НОД е асоциативна операция.
НОД(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, защото тогава естествените числа стават пълна дистрибутивна решетка с НОД като инфимум и НОК като супремум операция. Това разширение на дефиницията е съвместимо и с обобщението за комутативни пръстени, дадено по-долу.

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

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

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

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

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

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

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

Източници[редактиране | редактиране на кода]

  1. Сидеров, Пламен. Теория на числата за ученици. България, Издателство „Веди“, 2015. ISBN 978-954-8857-37-6. с. 12.