№2 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра ИС

отчет

по лабораторной работе №2

по дисциплине «Конструирование программ»

Тема: Элементы теории чисел.

Студент гр. 0375		Яблоков В.А.
Преподаватель		Копыльцов А. В.

Санкт-Петербург

2022

Цель работы:

Ознакомиться с канонической формой представления чисел, нахождением количества делителей произвольного числа, нахождением наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) нескольких чисел, нахождением евклидовых чисел.

Ход работы:

1. Выполнение примеров из теоретической части.

Примеры 1. Найти НОК и НОД следующих пар чисел:

a) 575 и 155.

575 = 5² * 23, 155 = 5 * 31,

НОК(575, 155) = 5^{max(2, 1)} * 23^{max(0, 1)} * 31^{max(0, 1)} = 17825,

НОД(575, 155) = 5^{min(2, 1)} * 23^{min(0, 1)} * 31^{min(0, 1)} = 5.

b) 840 и 188650.

840 = 2³ * 3 * 5 * 7, 188650 = 2 * 5² * 7³ * 11,

НОК(840, 188650) = 2³ * 3 * 5² * 7³ * 11 = 2263800,

НОД(840, 188650) = 2 * 5 * 7 = 70.

c) 4851 и 29106.

4851 = 3² * 7² * 11, 29106 = 2 * 3³ * 7² * 11,

НОК(4851, 29106) = 2 * 3³ * 7² * 11 = 29106,

НОД(4851, 29106) = 3² * 7² * 11 = 4851.

d) 975 и 616.

975 = 3 * 5² * 13, 616 = 2³ * 7 * 11,

НОК(975, 616) = 2³ * 3 * 5² * 11 * 13 = 600600,

НОД(975, 616) = 1.

Примеры 2. Найти НОК и НОД следующих пар чисел:

a) 440 и 6050.

440 = 2³ * 5 * 11, 6050 = 2 * 5² * 11²,

НОК(440, 6050) = 2³ * 5² * 11² = 24200,

НОД(440, 6050) = 2 * 5 * 11= 110.

b) 234 и 4125.

234 = 2 * 3² * 13, 4125 = 3 * 5³ * 11,

НОК(234, 4125) = 2 * 3² * 5³ * 11 * 13 = 321750,

НОД(234, 4125) = 3.

c) 66550 и 40131.

66550 = 2 * 5² * 11³, 40131 = 3² * 7³ * 13,

НОК(66550, 40131) = 2 * 3² * 5² * 7³ * 11³ * 13 = 2670718050,

НОД(66550, 40131) = 1.

d) 388 и 1647.

388 = 2² * 97, 1647 = 3³ * 61,

НОК(388, 1647) = 2² * 97 * 3³ * 61 = 600600,

НОД(388, 1647) = 1.

Примеры 3. Найти НОК и НОД для следующих наборов чисел:

a) 60, 350, 495.

60 = 2² * 3 * 5, 350 = 2 * 5² * 7, 495 = 3² * 5 * 11.

НОК(60, 350, 495) = 2² * 3² * 5² * 7 * 11 = 69300,

НОД(60, 350, 495) = 5.

b) 265, 104, 93.

265 = 5 * 53, 104 = 2³ * 13, 93 = 3 * 31.

НОК(265, 104, 93) = 2563080,

НОД(265, 104, 93) = 1.

c) 2100, 630, 5880, 9450.

2100 = 2² * 3 * 5² * 7, 630 = 2 * 3² * 5 * 7, 5880 = 2³ * 3 * 5 * 7², 9450 = 2 * 3³ * 5² * 7.

НОК(2100, 630, 5880, 9450) = 2³ * 3³ * 5² * 7² = 264600,

НОД(2100, 630, 5880, 9450) = 2 * 3 * 5 * 7 = 210.

d) 700, 495, 104.

60 = 2² * 5² * 7, 495 = 3² * 5 * 11, 104 = 2³ * 13.

НОК(700, 495, 104) = 2³ * 3² * 5² * 7 * 11 * 13 = 69300,

НОД(700, 495, 104) = 1.

e) 103, 260, 121.

103 = 103, 260 = 2² * 5 * 13, 121 = 11².

НОК(103, 260, 121) = 2² * 5 * 11² * 13 * 103 = 3240380,

НОД(103, 260, 121) = 1.

Пример 4. Проверить, какие из приведенных простых чисел при вычитании 1 являются евклидовыми:

10 = 2 * 5, 28 = 2² * 7, 30 = 2 * 3 * 5, 42 = 2 * 3 * 7, 52 = 2² * 13, 58 = 2 * 29, 70 = 2 * 5 * 7.

Таким образом, числа 11, 31, 43, 59, 71 будут евклидовыми при вычитании единицы.

2. Нахождение трёх трёхразрядных евклидовых чисел.

Возьмем простые числа: 101, 103, 107, 181, 263. Вычтем из них единицу и представим в каноническом разложении:

100 = 2 * 5²,

102 = 2 * 3 * 17,

106 = 2 * 53,

180 = 2² * 3² * 5,

262 = 2 * 131.

Таким образом, были найдены три трехразрядных евклидовых числа: 102, 106, 262.

Выводы:

В данной работе были отработаны навыки нахождения канонической формы числа, НОК и НОД чисел, а также нахождения евклидовых чисел.