Най-голям общ делител: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Ред 10:
По принцип най-големите общи делители могат да се пресметнат, като се разложат двете числа на [[просто число|прости]] множители и се сравнят множителите, като в следния пример: за да се изчисли НОД(18,84), се разлагат числата на прости множители 18 = 2.3<sup>2</sup> и 84 = 2<sup>2</sup>.3.7 и се установява, че сечението е 2.3. Следователно НОД(18,84) = 6. На практика този метод е приложим само за малки числа. Разлагането на прости множители отнема прекалено много време.
Много по-ефективен е [[Алгоритъм на Евклид|Алгоритъмът на Евклид]]{{Br}}
1) За делимо се взима по-голямото число а за делител - по-малкото число.{{Br}}
2) Делителя от своя страна се дели на остатъка от частното{{Br}}
3) Това се повтаря до тогава, докато частното има остатък. {{Br}}
{{Br}}
Делителя, при който частното няма остатък е НОД.{{Br}}
{{Br}}
Използвайки за илюстрация горният пример - '''НОД(18,84)''' - получаваме:{{Br}}
<math>84 : 18 = 4,12</math>{{Br}}
<math>18 : 12 = 1,6</math>{{Br}}
<math>12 : 6 = 0</math>{{Br}}
'''НОД = 6'''
== Свойства ==
| |||