НОД. Алгоритм Евклида. НОК

Определение 3. Всякое целое число 0, делящее одновременно целые ,..., над общим делителем этих чисел.

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

1)

2) .

Предложение. НОД чисел ,..., определен однозначно с точностью до знака (т.е. если – НОД чисел ,..., , то – – тоже НОД этих чисел).

Доказательство: пусть , - НОД чисел ,..., и (т. к. НОД делится на общий делитель этих чисел) = или = - .

В дальнейшем условимся рассматривать только положительные значения НОД и обозначать = (,..., ).

Для нахождения НОД существует алгоритм, который был дан Евклидом. Описав способ нахождения НОД, мы доказываем тем самым существование НОД.

Алгоритм Евклида базируется на следующих леммах:

Лемма 1. Если , то (, ) =

Доказательство: 1) и - общий делитель и .

2) пусть - общий делитель и .

, (, ) = .

Лемма 2. Если = + , то (, ) = (, ) 0

Доказательство: пусть (, ) = , тогда

1) из и , = -

2) и , - общий делитель и

= (, ).

(, ) = (, ).

Алгоритм Евклида

Пусть и - положительные числа, > >0. Разделим на , по теореме о делении с остатком: = + , 0 < .

. =0, т. е. = .

. 0, то получаем ряд равенств:

= + ; 0 < < (если =0, то процесс заканчивается).

= + 0< <

- - - - - - - - - - - - - - - - - - - - - -

(I) = + 0< <

=

Процесс заканчивается, когда мы получаем =0.

Последнее неизбежно, т. к. остатки, получаемые в процессе деления неотрицательны и убывают; следовательно, на каком-то шаге получим деление без остатка.

В силу леммы 2: (, ) = (, ) = (, ) = …= (, ) = .

Вывод: (, ) двух чисел равен последнему неравному нулю остатку в процессе алгоритма Евклида.

Пример. Найти (185, 55)= 5.

Задача отыскания НОД конечного множества чисел ,..., сводится к нахождению НОД для двух чисел.

Теорема 1. Если (, )= ; (, )= , …, (, )= , то

(,..., )= . (Доказать самостоятельно).

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

. Пусть 0, Z.

(, )= (, )

Применим алгоритм Евклида = +

= +

- - - - - - - - - - - -

= +

=

(, )= = (, ) .

. Пусть - любой общий делитель и , (; )=

(, )= ( ; )= (; ) св.2

Свойства НОК

Определение 5. Целое число 0 называется ОК чисел ,..., , если оно делится на из данных чисел.

Среди совокупности ОК чисел особую роль играет одно число, называемое НОК.

Определение 6. Целое число называется НОК чисел ,..., , если

1) ОК(,..., )

2) ОК этих чисел , т.е. …, ().

Возникает вопрос о рациональном способе нахождения НОК. Один из практических способов – использование теоремы, которая устанавливает связь НОК и НОД.

Теорема. НОК двух чисел равно их произведение, деленное на НОД этих чисел.

.

Доказательство: пусть =ОК = .

– кратно и

Пусть

, т. е. где

=

НОК получим при или

Вывод: совокупность общих кратных двух чисел совпадает с совокупностью кратных их общего наименьшего кратного.

Простые числа

Всякое целое число, больше 1, имеет не менее 2-х делителей, именно 1 и само себя.

Определение 1. Нaтуральное число p>1 называется простым, если p не имеет натуральных делителей, отличных от 1 и p.

Определение 2. Натуральное число a>1 называется составным, если a имеет, по крайней мере, один натуральный делитель, отличный от 1 и а.

1 не является ни простым, ни составным (т.к. имеет всего один натуральный делитель).

Первые простые числа в натуральном ряду: 2, 3, 5, 7, 11, 13, …

Простые числа – это элементы, при помощи, умножения которых строятся натуральные числа (>1); поэтому одной из важнейших задач теории чисел является изучение свойств простых чисел.

Свойства простых чисел:

1. p n, n N, n 1 p=n

Доказательство: пусть p n p имело бы 3 делителя 1, p, n, что невозможно, т.к. p- простое.

2. p₁, p₂ – различные простые числа p₂ не p₁

Доказательство: p₂ – простое p₂ имеет делитель 1 и p₂, но p₂ p₁ p₂

не p₁

3. n N, p – простое n p или (n, p)= 1

Доказательство: пусть (p, n)= d p- простое число d= 1 или d = p, d = 1 (d, n) 1; d = p n d, т.е. n p

4. ab p a p b p

Доказательство: если a p – то утверждение теоремы справедливо, если a

не p (a, p) = 1 ab p b p

5. Если произведение нескольких сомножителей p, то, по крайней мере, один из сомножителей p.(обобщение свойства 4)

Теорема 1. Для натурального числа a>1 наименьший отличный от единицы делитель есть число простое.

Доказательство: пусть q – наименьший 1 делитель натурального числа a>1; если бы q было составным, то оно имело бы некоторый делитель q₁, с условием 1 < q₁ < q, но a q и q a q₁ , а это противоречит предположению относительно q.