2. Нод и нок целых чисел. Свойства. Алгоритм Евклида.

§3. Нод и нок, алгоритм Евклида

Определение. Число d называется общим делителем чисел если

Определение. Наибольшим общим делителем целых чисел называется такой их общий натуральный делитель, который делится на любой их общий делитель. Обозначают:

d = .То есть d=( ), если

1) d € N,

2)d - общий делитель чисел

3)если с - общий делитель чисел , то d⁞c.

Определение. Число М называется общим кратным целых чисел если оно делится на каждое из этих чисел.

Определение. Наименьшим общим кратным целых чисел называется такое их общее натуральное кратное m, которое делит любое их общее кратное. Обозначают: m = [

Итак, m = [ ], если

1. m€N

2. m - общее кратное чисел

3. если М- общее кратное чисел , то M⁞m.

Пример: (16,30,12)= 2; [16,30,12] = 16*5 *3 = 240.

Лемма. Если a, b€Z, b≠0 и a=bq + r, то (а,b)=(b,r). Доказательство. Пусть (a,b)= , (b,r)= .Так как a⁞ то r=a-bq . Следовательно, - общий делитель чисел b и r, поэтому их наибольший общий делитель

= (b,r) .

Так как b⁞ , r⁞ ,то a⁞ ,и - общий делитель чисел а и b.

Поэтому ⁞ . Из того, что ⁞ , ⁞ ] и , следует, что

=

Пусть a,b€Z, b≠0. По теореме о делении с остатком

a=b . Если , то

b= . Если , то

= . И так далее.

…………..

=

=

Этот процесс не может быть бесконечным, так как не может быть бесконечной убывающая последовательность неотрицательных целых чисел: . Поэтому после нескольких шагов получим остаток, равный нулю. Пусть

Полученную цепочку равенств называют алгоритмом Евклида. Алгоритм Евклида, применённый к целым числам а и b, где b≠0, заключается в том, что сначала а делим на b с остатком, а затем каждый раз делим делитель на новый остаток, пока ни получим остаток, равный нулю.

Теорема. Последний, не равный нулю остаток в алгоритме Евклида, применённом к целым числам а и b, где b≠0, есть их наибольший общий делитель (НОД).

Доказательство. Применяя лемму к первому, второму и так далее равенствам алгоритма Евклида, имеем:

(а, b)=(b, )=( )= ... = ( )= , так как

Из теоремы следует существование НОД двух чисел, если хотя бы одно из них не равно нулю.

Свойства НОД.

1.Если a⁞b, то (a, b) = |b|. Действительно, - натуральный общий делитель а и b, который делится на любой их общий делитель (так как на него делится b).

2.НОД двух чисел линейно выражается через эти числа. То есть если (a, b)=d, то существуют u, v €Z, что d=аu + bv (линейная форма НОД).

Доказательство. Из первого равенства алгоритма Евклида . Подставив вместо это выражение во второе равенство, получим: Подставив вместо полученные выражения в третье равенство, выразим через а и b. Продолжая так дальше, получим выражение = (a,b) через а и b.

Заметим, что можно было получить это выражение, начиная с конца алгоритма. Из предпоследнего равенства . Последовательно двигаясь снизу вверх, выражаем через предыдущие остатки, пока ни получим выражение его через а и b.

Примеры. Найдём НОД чисел а и b и выразим его линейно через эти числа. 1) а = 1173, b = 323; а = b*3 + , =204 ; b= , =119;

Итак, (a, b)= d = 17. Выразим его линейно через а и b. Из первого равенства . Подставив в равенство для b, находим . Далее:

2)

НОД чисел а и b равен 23. 23 = 1058-345*3 = 1058-(l 403-1058)*3 =-3*1403 + +4*1058 = -За + 4b.

3.Если (а,b)= d, n€N, то (na;nb)= nd.

Верность утверждения следует из алгоритма Евклида для чисел а и b, если каждую строчку его умножить на n.

4.Если (a,b)=d, а⁞n, b⁞n, n€N, то . Для доказательства

достаточно каждую строчку алгоритма Евклида для чисел а и b разделить на n. В частности, .

5.

Доказательство. Пусть

делятся на . Следовательно, и поэтому их НОД .

Так как делятся и на и их наибольший общий делитель )= . Получили, что .

6.Наибольший общий делитель чисел , где не все , равны нулю, существует, и единственный.

Существование следует из теоремы о последнем, не равном нулю остатке в алгоритме Евклида и свойства 5. Единственность - из определения НОД и свойства 6 делимости чисел.

Свойства НОК.

1. .

2.Если k- натуральное, то

3.Если k- натуральное, a⁞k, b⁞k, то

4.Если (a,b)=1, то [a,b]=ab.

Замечание. Свойство 1 доказывается аналогично свойству 5 НОД; остальные свойства можно доказать позже, используя следствие 3 из основной теоремы арифметики.