LCM (m, n).
Набір цілих чисел <# «13» src=«doc_zip122.jpg» /> називається взаємно простими числами <# «25» src=«doc_zip123.jpg» />
тут - різні прості числа, а і невід'ємні цілі числа (вони можуть бути нулями, якщо в розкладанні відсутній). Тоді НСД та НСК виражаються формулами:
Для будь-яких m і n
це окремий випадок більш загальної теореми:
Якщо - ненульові раціональні числа, тоді
Найбільший спільний дільник чисел m і n може бути визначений як найменший позитивний елемент всіх їх лінійних комбінацій:
і, таким чином (m, n) представимо у вигляді лінійної комбінації <# «21» src=«doc_zip135.jpg» />.
Це співвідношення називається співвідношенням Безу, а коефіцієнти u і v-коефіцієнтами Безу. Коефіцієнти Безу ефективно обчислюються розширеним алгоритмом Евкліда <# «14» src=«doc_zip136.jpg» />, Породжена набором,-циклічна <# «21» src=«doc_zip138.jpg» />
5.1 Алгоритм Евкліда для цілих чисел
Нехай і - цілі числа, не рівні одночасно нулю, і послідовність чисел
визначена тим, що кожне - це залишок від ділення попереднього числа на попереднє, а передостаннє ділиться на останнє остачі, тобто
Тоді НОД (a, b), найбільший спільний дільник і, дорівнює, останньому ненульовому члену цієї послідовності.
Існування таких, то є можливість розподілу із залишком на для будь-якого цілого і цілого, доводиться індукцією <# «justify"> Нехай
,
тоді НСД (a, b)=НСД (b, r).
Доказ
НОД (0,)=для будь-якого ненульового (тому 0 ділиться на будь-яке ціле число, крім нуля).
Простіше сформулювати алгоритм Евкліда так: якщо дано натуральні числа і і, поки що виходить позитивне число, по черзі віднімати з більшого менший, то в результаті вийде НОД.
Для ілюстрації, алгоритм Евкліда буде використаний, щоб знайти НСД a=1071 і b=462. Для початку, від 1071 віднімемо кратне значення 462, поки не отримаємо різницю менше ніж 462. Ми повинні двічі відняти 462 , (q 0=2), залишаючись із залишком 147
=2 Ч 462 + 147.
Потім від 462 віднімемо кратне значення 147, поки не отримаємо знаменник менше ніж 147. Ми повинні тричі відняти 147 (q 1=3), залишаючись із залишком 21.
=3 Ч 147 + 21.
Потім від 147 віднімемо кратне значення 21, поки не отримаємо знаменник менше ніж 21. Ми повинні сім разів відняти 21 (q 2=7), залишаючись без залишку.
=7 Ч 21 + 0.
Таким чином, послідовність a> b> R1> R2> R3> R4> ...> Rn в даному конкретному випадку буде виглядати так:
> 462> 147> 21
Так як останній залишок дорівнює нулю, алгоритм закінчується числом 21 і НОД (1071, 462)=21.
У табличній формі, кроки були наступні:
Крок kРавенствоЧастное і остаток01071=q 0462 + r 0 q 0=2 і r 0=1471462=q 1147 + r 1 q 1=3 і r 1=212147=q 21 лютого + r 2 q 2=7 і r 2=0; алгоритм закінчується
.2 Розширений алгоритм Евкліда і співвідношення Безу
