Теорема о делении с остатком в кольце целых чисел

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

Определение 1.

Целое число делится на ненулевое число если существует такое целое число с, что . Обозначают:

Определение 2.

Разделить целое число на ненулевое число с остатком – это значит найти два целых таких, чтобы выполнились два условия:

Теорема о делении с остатком

Каковы бы не были всегда возможно и притом единственным способом разделить на с остатком, т. е.

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

1) существован

а) Пусть

Рассмотрим кратные числа (т. е. Если отметить эти числа, то среди этих чисел найдем наибольшее кратное числа и обозначим , притом

Таким образом след-м за будет

т. е.

. Обозначим за

.

б) Пусть

Если .

По предыдущему случаю а)

2) (от противного)

Предположим, что

так как , то Противоречие. Значит допущение неверно Ч. т.д.

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

Определение 4. Целое число называется НОД чисел , если выполнены два условия:

1) является общим делителем этих чисел;

делится на любой другой общий делитель чисел

Обозначают:

Определение 5. Пусть а1,а2,…,аn целые числа отличные от 0. Цел. число m называется НОК этих чисел, если выполнены два условия:

1) является общим кратным этих чисел;

делит любое другое общее кратное чисел

Обозначают:

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

1) Если , то не существует.

2) Наибольший по величине положительный общий делитель целых чисел является

3) Пусть , если

4) Если , то существует такая пара целых чисел таких, что – линейное представление НОД через исходные числа

5) Пусть , где

Свойства НОК (аналогичны св-вам НОД).

Теорема: НОК двух целых чисел a и b равно произведению этих чисел, деленному на их НОД, т. е. p1α p2α …pnα

Способы нахождения НОД и НОК:

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

Теорема. НОД целых чисел равен последнему ненулевому остатку при делении по алгоритму Евклида.

2. Нахождение нод и нок с помощью разложения чисел a и b на простые множители.

Каноническое представление целых чисел a и b

где pi — различные простые множители, αi ,βi – степени pi в разложении чисел a и b.

НОД (a, b) =

НОК [a, b] =

Примечание:

Лемма 1. то

Лемма 2.Если целые числа связаны равенством то

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

Пусть Разделим с остатком, т. е.

…

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

Теорема: Натуральное число n является составным, если имеет хотябы один простой делитель не превосходящей .

Пример. Найдите НОД и НОК трех чисел 420,126 двумя способами.

Решение:

1сп. 420 126

378

126 42

126 3

НОД (420,126) =42 0

= 1260

2сп.

НОД(420,126)=21 ·31 ·50· 71=42

НОК[420,216]= 22·32·51·71= 1260