Учебные материалы по математике | Теорема о делении с остатком в кольце целых чисел | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

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


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

210

105

35

7

1

2

2

3

5

7

126

63

21

7

1

2

3

3

7

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

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

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020