МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное образовательное
учреждение высшего образования
«Юго-Западный государственный университет»
Практическая работа №1
По дисциплине «Элементы алгебры и теории чисел»
Вариант №6
Выполнил: Бунина А.В.
студент группы ИБ-01б
Проверил: Добрица В.П.
профессор
Курск, 2021
Задание1. Вычислить НОД d = (588;2058;2849) двумя способами:
1 способ:
Нахождение НОД с помощью разложения чисел на простые множители. Для того, чтобы найти наибольший общий делитель двух чисел методом разложения на множители, необходимо перемножить все простые множители, которые получаются при разложении этих двух чисел и являются для них общими.
Разложение чисел:
588 = 2 × 2 × 3 × 7 × 7
2058 = 2 × 3 × 7 × 7 × 7
2849 = 7 × 11 × 37
НОД (588;2058;2849) = 7.
2 Способ:
Алгоритм
Евклида позволяет с легкостью вычислить
наибольший общий делитель для двух
положительных чисел. Основан
это алгоритм на применении следующей
теоремы: НОД нескольких чисел
равен числу
,
которое находиться при последовательном
вычислении НОД (
,
НОД (
… НОД (
Введем
переменные:
.
Найдем
НОД
(588;2058) =
|
2058 |
588 |
|
|
1764 |
3 |
|
588 |
294 |
|
|
588 |
2 |
|
|
0 |
|
|
|
,
т. к. 294 последний положительный остаток.
Найдем
НОД
(
,
т.е. НОД (294; 2849) =
|
|
|
|
2849 |
294 |
|
|
|
|
|
|
2646 |
9 |
|
|
|
|
|
294 |
203 |
|
|
|
|
|
|
203 |
1 |
|
|
|
|
|
203 |
91 |
|
|
|
|
|
|
182 |
2 |
|
|
|
|
|
91 |
21 |
|
|
|
|
|
|
84 |
4 |
|
|
|
|
|
21 |
7 |
|
|
|
|
|
|
21 |
3 |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
,
т.к. 7 последний положительный остаток.
Найдем
их общий НОД
,
где
.
Получаем, что
294 |
7 |
294 |
42 |
0 |
|
.
НОД трех чисел является цифра 7.
(Это уже лишнее действие в силу теоремы.)
Ответ: НОД d = (588;2058;2849) = 7
Исправление:
2 Способ:
Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Основан это алгоритм на применении следующей теоремы: НОД нескольких чисел равен числу , которое находиться при последовательном вычислении НОД ( , НОД ( … НОД (
Введем переменные: .
Найдем НОД (588;2058) =
|
2058 |
588 |
|
|
1764 |
3 |
|
588 |
294 |
|
|
588 |
2 |
|
|
0 |
|
|
|
, т. к. 294 последний положительный остаток.
Найдем НОД ( , т.е. НОД (294; 2849) =
|
|
|
|
2849 |
294 |
|
|
|
|
|
|
2646 |
9 |
|
|
|
|
|
294 |
203 |
|
|
|
|
|
|
203 |
1 |
|
|
|
|
|
203 |
91 |
|
|
|
|
|
|
182 |
2 |
|
|
|
|
|
91 |
21 |
|
|
|
|
|
|
84 |
4 |
|
|
|
|
|
21 |
7 |
|
|
|
|
|
|
21 |
3 |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
, т.к. 7 последний положительный остаток.
Ответ: НОД d = (588;2058;2849) = 7