Уикипедия

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

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
м интервал; козметични промени
мРедакция без резюме
Ред 1:
{{без източници}}
'''Най-голям общ делител''' (НОД) на две [[цяло число|цели числа]], поне едното от които е различно от нула, в [[математика]]та е най-голямото цяло число, което [[делителДелене|дели]] и двете числа без остатък.
 
Най-големият общ делител на ''a'' и ''b'' се означава като НОД(''a'', ''b''), GCD(''a'', ''b'') или понякога просто (''a'', ''b''). Например, НОД(12,  18) = 6, НОД(−4, 14) = 2 и НОД(5,  0) = 5. Две числа се наричат „[[взаимно прости числа|взаимно прости]]“, ако техният най-голям общ делител е 1, т.е. Напримернямат общ [[делител]], различен от 1. Например 9 и 28 са взаимно прости.
 
Най-големият общ делител е полезен при съкращаването на обикновени [[дроби]]. Например в
Ред 9:
 
== Изчисляване на НОД ==
По принцип най-големите общи делители могат да се пресметнат, като се разложат двете числа на [[просто число|прости]] множители и се сравнят множителите, като в следния пример: за да се изчисли НОД(18,84), се разлагат числата на прости множители 18&nbsp;=&nbsp;2т.нар.3<sup>2</sup> и 84&nbsp;=&nbsp;2<sup>2</sup>.3.7[[факторизация]]) и се установява,сравнят че сечението е 2.3. Следователно НОД(18,84)&nbsp;=&nbsp;6множителите.
 
Например: за да се изчисли НОД(18, 84), се разлагат числата на прости множители 18&nbsp;=&nbsp;2×3<sup>2</sup> и 84&nbsp;=&nbsp;2<sup>2</sup>×3×7 и се установява, че сечението е 2×3. Следователно НОД(18,84)&nbsp;=&nbsp;6.
Много по-ефективен е [[Алгоритъм на Евклид|Алгоритъмът на Евклид]]:▼
 
▲Много по-ефективен е [[Алгоритъм на Евклид|Алгоритъмъталгоритъмът на Евклид]]:
# За делимо се взима по-голямото число, а за делител – по-малкото число.
# Делителят от предишната стъпка се разделя на получения остатък.
Line 19 ⟶ 21:
{{Br}}
Използвайки за илюстрация примерът описан по-горе – '''НОД(18,84)''' – получаваме:
: 84: /18 = 4 и остатък 12
: 18: /12 = 1 и остатък 6
: 12: /6 = 2 без остатък
 
=> '''НОД(18,84) = 6'''
Line 28 ⟶ 30:
* Всеки общ делител на ''a'' и ''b'' е делител на НОД(''a'',&nbsp;''b'').
 
* НОД(''a'',&nbsp;''b''), където ''a'' или ''b'' не е нула, може да се дефинира еквивалентно по друг начин като най-малкото положително цяло число ''d'', което може да се запише във формата: ''d''&nbsp;=&nbsp;''a''·''p''&nbsp;+&nbsp;''b''·''q'', където ''p'' и ''q'' са цели числа. Този израз се нарича [[тъждество на Безу]]. Числата ''p'' и ''q'' могат да се изчислят чрез [[Разширен алгоритъм на Евклид|разширения алгоритъм на Евклид]].
 
* Ако ''a'' е делител на произведението ''b''·''c'', и НОД(''a'',&nbsp;''b'')&nbsp;=&nbsp;''d'', то ''a''/''d'' е делител на ''c''.
Взето от „https://bg.wikipedia.org/wiki/Най-голям_общ_делител“.