ЭАиТЧ_ПР1_Простые и составные числа, каноническое представление составного числа

МИНОБРНАУКИ РОССИИ

Федеральное государственное образовательное учреждение высшего образования

“Юго–Западный государственный университет”

Кафедра информационной безопасности

Лабораторная работа №1

По дисциплине “Элементы алгебры и теории чисел”

По теме “ Простые и составные числа, каноническое представление составного числа”

Выполнил: студент группы ИБ-11б

Гребенникова А.И.

Проверил проф. Добрица В.П.

Курск 2023г.

Цель: изучить понятия простого и составного числа, теорему о бесконечности множества простых чисел, теорему деления с остатком, научиться проверять простоту числа и находить каноническое представление составного числа.

Ход работы:

Задание 1. Найти все простые числа между числами a, b:

Вариант 5. a =110; b =140;

Выпишем эти числа и применим «решето Эратосфена».

110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140

Вычеркнем сначала числа, кратные 2. Останутся следующие числа.

111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139

Теперь вычеркнем числа, кратные 3. Получим последовательность чисел

113, 115, 119, 121, 125, 127, 131, 133, 137, 139

Затем вычеркнем числа, кратные 5, получим:

113, 119, 121, 127, 131, 133, 137, 139

Теперь вычеркнем числа, кратные 7. Получим:

113, 121, 127, 131, 137, 139

Вычеркнем числа, кратные 11:

113, 127, 131, 137, 139

Проверять делимость на числа больше 11 нет необходимости, поскольку 12²>140. Итак, мы получили конечную последовательность простых чисел 113, 127, 131, 137, 139

Задание 2. Разложить на простые множители:

Вариант 5. n =14!

Вынесем сначала 2 из тех множителей, которые кратны 2, затем вынесем еще раз 2 из оставшихся множителей, кратных 2. Из оставшихся после этого множителей вынесем 3. Получим следующее представление.

Задание 3. Выясните, является ли число простым или составным:

Вариант 5. a = 2667

Проверяем делимость этого числа на простые числа, квадрат которых не превосходит а. Это простые числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Число 2667 делится на 3 и 7, а значит, оно является составным.

Задание 4. Найти высшие степени чисел 2, 3, 5, 7, 11, 13, на которые делится число n!:

Вариант 5. n =34!. По методу из решения задачи 2 вынесем сначала 2 из множителей, кратных 2, затем 3, 5, 7, 11 и 13 по аналогии.

Таким образом, высшими степенями чисел являются для 2 – 32, для 3 – 15, для 5 – 7, для 7 - 4, для 11 – 3 и для 13 – 2.

(Есть формула определения показателя простого множителя в разложении числа n!)

При помощи формулы , где [ будет равен 0.

Вычислим вхождение числа 2:

Вычислим вхождение числа 3:

Вычислим вхождение числа 5:

Вычислим вхождение числа 7:

Вычислим вхождение числа 11:

Вычислим вхождение числа 13:

Таким образом, высшими степенями чисел являются для 2 – 32, для 3 – 15, для 5 – 7, для 7 - 4, для 11 – 3 и для 13 – 2.

Задание 5. Представить в канонической форме число:

Вариант 5. a =1101433;

Число 1101433 является простым числом, поскольку имеет только 2 делителя: 1 и 1101433(т.е. себя), а это значит, что его нельзя разложить на простые множители и записать каноническую форму. (Чем Вы это подтвердите?)

Чтобы определить является ли число простым, необходимо его поделить на 2, затем на 3, 4, ... n, до тех пор, пока n не станет равным самому числу. (Есть более рациональный способ. В частности по правилу Эратосфена). Если это число разделится без остатка только на само себя, то оно является простым. 1101433 - простое число так как у него только 2 делителя: 1 и 1101433 (оно само). Число считается простым, если оно имеет ровно два делителя. (Неужели проверяли все эти делимости?)

Решето Эратосфена действительно было бы более рациональным решением. Однако чтобы найти число 1101433 как описанным мной выше способом, так и с помощью решета Эратосфена вручную потребуется огромное кол-во времени. Я воспользовалась таблицей простых чисел, чтобы определить, является ли данное число простым.

Задание 6. Разделить число а на положительное число b с остатком.

Вариант 5. a =2501313, b =140;

Поделим число a на число b столбиком («уголком»)

Таким образом, 2501313=140*17866+73