Уикипедия

Най-голям общ делител: Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
м интервал; козметични промени
Ред 2:
'''Най-голям общ делител''' (НОД) на две [[цяло число|цели числа]], поне едното от които е различно от нула, в [[математика]]та е най-голямото цяло число, което [[делител|дели]] и двете числа без остатък.
 
Най-големият общ делител на ''a'' и ''b'' се означава като НОД(''a'', ''b''), GCD(''a'', ''b'') или понякога просто (''a'', ''b''). Например, НОД(12, 18) = 6, НОД(−4−4, 14) = 2 и НОД(5, 0) = 5. Две числа се наричат „[[взаимно прости числа|взаимно прости]]“, ако техният най-голям общ делител е 1. Например, 9 и 28 са взаимно прости.
 
Най-големият общ делител е полезен при съкращаването на обикновени [[дроби]]. Например в
Ред 19:
{{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>,&nbsp;''b'') = НОД(''a''<sub>1</sub>,&nbsp;''b'')·НОД(''a''<sub>2</sub>,&nbsp;''b'').
 
* НОД на три числа може да се пресметне като НОД(''a'',&nbsp;''b'',&nbsp;''c'') = НОД(НОД(''a'',&nbsp;''b''),&nbsp;''c'') = НОД(''a'',&nbsp;gcd(''b'',&nbsp;''c'')). Следователно НОД е [[асоциативност|асоциативна]] операция.
 
* НОД(''a'',&nbsp;''b'') е тясно свързано с [[най-малко общо кратно|най-малкото общо кратно]] НОК(''a'',&nbsp;''b''): в сила е
::НОД(''a'',&nbsp;''b'')·НОК(''a'',&nbsp;''b'')&nbsp;=&nbsp;''a''·''b''.
:Тази формула често се използва за пресмятане на общи кратни: първо се изчислява НОД по алгоритъма на Евклид и след това се дели произведението на зададените числа на техния НОД. Валидни са следните варианти на [[дистрибутивност]]:
Ред 44:
::НОК(''a'',&nbsp;НОД(''b'',&nbsp;''c''))&nbsp;=&nbsp;НОД(НОК(''a'',&nbsp;''b''),&nbsp;НОК(''a'',&nbsp;''c'')).
 
* Полезно е да се дефинира НОД(0,&nbsp;0)&nbsp;=&nbsp;0 и НОК(0,&nbsp;0)&nbsp;=&nbsp;0, защото тогава [[естествено число|естествените числа]] стават [[пълна решетка|пълна]] [[дистрибутивна решетка|дистрибутивна]] [[решетка (теория на множествата)|решетка]] с НОД като инфимум и НОК като супремум операция. Това разширение на дефиницията е съвместимо и с обобщението за комутативни пръстени, дадено по-долу.
 
* В [[декартова координатна система]] НОК(''a'',&nbsp;''b'') може да се интерпретира като броя точки с цели координати върху [[отсечка]]та, свързваща началото(0,&nbsp;0) и (''a'',&nbsp;''b''), без (0,&nbsp;0).
 
== НОД в комутативни пръстени ==
Ред 59:
Елементите <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'' нямат най-голям общ делител. ([[Ернст Кумер]] използва този идеал като заместител на НОД в работата си върху [[Последна теорема на Ферма|последната теорема на Ферма]]<!--although he envisioned it as the set of multiples of some hypothetical, or ''ideal'', ring element ''d'', whence the ring-theoretic term.-->)
 
== Вижте също ==
 
* [[Най-малко общо кратно]]
* [[Най-малък общ знаменател]]
* [[Двоичен алгоритъм за НОД]]
 
[[Категория:Алгебра]]
[[Категория:Теория на числата]]
Взето от „https://bg.wikipedia.org/wiki/Най-голям_общ_делител“.