Най-голям общ делител – Уикипедия

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

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

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

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

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

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

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

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

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

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

• Най-малко общо кратно
• Най-малък общ знаменател
• Двоичен алгоритъм за НОД