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

Най-голям общ делител (GCD) на две числа m и п е най-общ делител на тях. [1] Пример: за номера 70 и 105 е най-общ делител на 35.

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

Възможна означават най-голям общ делител на номера М и Н:

Концепцията за най-голям общ делител естествено да се отнесе за групи от повече от две числа.

Най-малко общо кратно

NOC за ненулеви числа m и п са винаги съществува и е свързан с GCD следната връзка:

Това е специален случай на по-обща теорема: ако 1. 2. .... а п, а _ \ точки, a_> - броят на различна от нула, D - някой от тяхното общо кратно, по следната формула притежава:

Сравнително-председател

М и н се наричат ​​взаимно прости. ако нямат общи делители, различни от единство. За тези номера GCD (m, п) = 1. Обратно, ако GCD (m, п) = 1, тогава числата са взаимно прости.

По същия начин, числата на 1. 2. ... а к, а _ \ точки a_>. където к ≥ 2. казва, че е сравнително прост. ако най-голямото им общ делител е равен на единица.

Необходимо е да се направи разграничение на концепцията за взаимно лекота. когато GCD набор от числа е равно на 1 и по двойки сравнително премиер. където GCD е 1 за всяка двойка номера от комплекта. От двойки сравнително премиер предполага простота, но не и обратното. Например, GCD (6,10,15) = 1, но чифт някоя от тази група не са относително прости.

Ефективните начини за изчисляване на НОД на две числа са на алгоритъма на Евклид и двоичен алгоритъм.

където р 1. .... р к, \ точки, P_> - различни прости числа, и г 1. .... г к \ точки, d_> и д 1. .... д к, \ точки, e_> - не-отрицателни числа (те могат да бъдат нула, ако съответните просто отсъства в разширяването). След GCD (m, п) и NOC (m, п) се изчислява по формулата:

Ако повече от две числа: а 1. 2. ... а п, а _ \ точки a_>. тяхната GCD е следния алгоритъм:

  • Основна функция: най-голям общ делител на пит се дели на всеки общ делител на тези номера. Пример: за номера 12 и 18, най-голям общ делител е равно на 6; е неделими от всички общи делители на числата 1, 2, 3, 6.
    • Следствие 1: множество общи делители на m и п съвпада с GCD комплект делители (п т.).
    • Следствие 2: множество общи кратни на m и п съвпада с набор от множествена LCM (т н.).
  • Ако m е разделена от п. на GCD (т. н) = N. По-специално, GCD (п. N) = N.
  • (. А ⋅ m на ⋅ п) = | а | ⋅ (т н.) - общ фактор може да се приема като знак за GCD.
  • Ако D = (т. N). след разделяне на броя на D са взаимно прости, т.е. (m Г. п D) = 1>, >> \ дясно) = 1>. Това означава, наред с другото, че да донесе ударът на който не може да бъде принуден да кажа, че е необходимо да се разделят на числителя и знаменателя с тяхната ГРУ.
  • Multiplicativity. ако 1. 2, a_> са сравнително премиер, тогава:
(А 1 ⋅ на 2. б) = (а 1. б) ⋅ (а 2. б) \ cdot a_, б) = (a_, б) \ cdot (a_, Ь)>
  • Най-голям общ делител на номера м и п може да се определи като най-малкото положително елемент от множеството на всички линейни комбинации от тях;
\ Десния \ >> и следователно (т. N) представено като линейна комбинация от числа м и п. (М. N) = ф ⋅ m + V ⋅ п. Това съотношение се нарича Bezout връзка. и коефициентите ф и V - Bezout коефициентите. Bézout коефициенти са изчислени ефективно удължава Алгоритъм на Евклид. Това твърдение може да се отнесе набори от естествени числа - значението му е, че подгрупа Z>. генерира набор ,а _ \ точки, а _ \ >>. - циклични и се генерира от един елемент: GCD (а1 а2, ... на ...).

Вариации и обобщения

Концепцията за делимост на числа естествено да се обобщи на произволна комутативен пръстен. като пръстенът на полиноми или Gaussian числа. Въпреки това, за да се определи GCD (а. В), като най-голям общ делител на. б е невъзможно, тъй като в такива пръстени, най-общо казано, не е определена връзка ред. Ето защо, като определението е взето GCD основната си собственост:

Най-общо делител GCD (а. В) се нарича общ делител, който е разделен на всички други общи фактори А и В.

За естествените числа нова дефиниция е еквивалентна на старите. За числа НОД в нов смисъл вече не е ясно: неговата противоположност брой също ще ГРУ. За Гаус номера няколко различни NOD се увеличава до 4.

НОД на два елемента от комутативен пръстен, най-общо казано, не трябва да съществува. Например, за следните елементи А и Б на пръстен Z [- 3] \ оставени [> \ полето]> не е най-голям общ делител на:

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