Добавил:

Qumorr Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича

Предмет:

Математические основы защиты информации

Файл:

МОЗИ_Лаб_06.docx

Скачиваний:

Добавлен:

09.04.2023

Размер:

305.73 Кб

Скачать

☆

<<< < Предыдущая 12 / 32 3 > Следующая >>>

5. Найти функцию Эйлера для чисел 8, 19, 20, 131.

ф(8) = (2³ - 2²) = 8 - 4 = 4 ф(19) = (19¹ - 19⁰) = 19 - 1 = 18 ф(20) = (2² - 2¹) * (5¹-5⁰) = 2 * 4 = 8 ф(131) = (131¹ – 131⁰) = 131 - 1 = 130

6. Найти функцию Эйлера для чисел (используйте разложение этих чисел на множители из задачи 4):

a. 711480

ф(711480) = ( 2³-2²) * (3¹-3⁰) * (5¹-5⁰) * (7² – 7¹) * (11² – 11¹) = 147840

b. 3025269

ф(3025269) = (3⁴ – 3³) * (13³-13²) * (17¹-17⁰) = 1752192

c. 10481625

ф(10481625) = (3² – 3¹) * (5³ – 5²) * (7¹ – 7⁰) * (11³ – 11²) = 4356000

7. Сократите сравнения:

a. 91* x = 105 mod 121 = 105

x = 105 / 91

b. 91* x = 105 mod 143 = 105

x = 105/ 91

c. 352 = 90 mod 131

в пункте с задания №7 допущена опечатка.

d. 135 = 528 mod 393 = 135

8. Задание на цепную дробь. Найти представление в виде цепной дроби для отношения: (7*x+11)/43, где x – номер студента в списке группы. Количество выполненных вариантов должно совпадать с количеством студентов в бригаде.

7*8+11/43 = 67/43 =1+

7*9+11/43 = 74/43 = 1 +

9. На какие цифры не может оканчиваться квадрат целого числа; куб целого числа?

Квадрат числа: 3,7,8

Куб числа: 2,3

10. Докажите, что пятая степень любого целого числа оканчивается на ту же цифру, что и само число.

Пусть дано число b, тогда:

Последняя цифра числа а = последней цифре числа, полученного при возведении в степень 5 последней цифры числа b.

1^5 = 1

2^5 = 32

3^5 = 243

4^5 = 1024

5^5 = 3125

6^5 = 7776

7^5 = 16897

8^5 = 32768

9^5 = 59049

что и требовалось доказать.

11. На какую цифру оканчивается сумма квадратов пяти последовательных целых чисел?

A^2+(a+1)^2+(a+2)^2+(a+3)^2+(a+4)^2=5a^2+20a+30

20a оканчивается на 0

30 на 0, сумма этих слагаемых = 0

Рассмотрим 5а^2

Один из множителей “5”, опираясь на правила умножения этого числа получим, что произведение будет оканчиваться на 0 или на 5.

Соответственно сумма квадратов пяти идущих подряд чисел оканчивается на 0 или на 5.

12. Докажите, что произведение пяти последовательных целых чисел делится на пять.

Произведение кратно 5, т.к. один из множителей: a(a+1)(a+2)(a+3)(a+4) будет обязательно кратен 5.

13. Докажите, что разность квадратов двух нечетных чисел делится на 8.

(2n+1)^2-(2m+1)^2=4n^2+4n+1-4n^2+4n-1=8n

Значит число делится на 8, т.к. это один из множителей

14. Найдите наименьшее натуральное число, которое делится на 2, 3, 4, 5, 6, 7, 8, 9 и 10.

Поскольку нас интересует наименьшее натуральное число, которое делится на 9 последовательных натуральных чисел, то, очевидно, эти натуральные числа должны быть наименьшими из возможных.

НОК (2,3,4,5,6,7,8,9,10)=2*3*2*5*7*2*3=6*10*7*6=2520.

15. Найдите наименьшее натуральное число, делящееся на 7 и дающее остаток 1 при делении на каждое из чисел 2, 3, 4, 5, 6.

301/7= 43

301/6= 50 + ост. 1

301/5= 60 + ост. 1

301/4 = 75 + ост. 1

301/3 = 100 + ост. 1

301/2 = 150 + ост. 1

16. При любом натуральном n найдите наибольший общий делитель чисел:

а) n^2 + 3n + 1 и n + 3;

б) 3n^4 + 6n^2 + 1 и n^3 + 2n.

а) Воспользуемся алгоритмом Эвклида

a = n^2+3n+1

b = n+3

n^2 +3n+1/n+3 = n (остаток 1);r1=1

n+3/rl=n+3/1=n+3 (остаток 0)

получим, что rl – НОД = 1

б) Воспользуемся алгоритмом Эвклида

a=3n^4+6n^2+1

b=n^3+2n

3n64+6n^2+1/n^3+2n=3n (остаток 1); rl=l

n^3 +2n/1 n^3+2n (остаток 0)

получим, что rl – НОД = 1.

17. Докажите, что наибольший общий делитель чисел а и b делится на любой их общий делитель.

Наибольший общий делитель двух целых чисел – это наибольшее целое число, делящее два данных целых числа. Значит, если оба числа имеют более одного общего делителя, то НОД этих двух чисел будет произведением всех общих делителей, => будет делиться на каждый из них, что и требовалось доказать.

18. Докажите, что три натуральных числа 4n-1, n и 2n-1 попарно взаимно просты.

Числа называются взаимно простыми, если их НОД равен единице и взаимно попарно простыми, если любые два из них взаимно просты, т.е. их НОД равен единице.

НОД(4n-1, n) = 1 по алгоритму Эвклида

НОД(4n-1, 2n-1) = 1 по алгоритму Эвклида

НОД(2n-1, n) = 1 по алгоритму Эвклида

=> эти числа действительно попарно взаимно простые, что и требовалось доказать.

19. Докажите, что при любом натуральном n: n^2(n^2-1) делится на 12;

n^2 (n^2 - 1) = n*n*(n-1)*(n+1) числа (n-1),n,(n+1) - это три числа, идущие по порядку, => одно из них обязательно делится на 3 остается доказать, что число делится на 4 если n четное, то n делится на 2 => n^2 делится на 4 если n нечетное, то (n+1) и (n-1) - четные => (n+1)(n-1) делится на 2*2, т. е. на 4. Мы доказали, что число делится и на 4, и на 3 (то есть, на 12).

20. Задание на понятие Вычета

Задание для вычетов x, y (см. свой вариант) по модулю 9

1) указать класс вычетов, которому они принадлежат.

2) заменить эти вычеты на:

2.1) наименьшие по абсолютной величине вычеты;

2.2) наименьшие неотрицательные вычеты;

2.3) вычеты, входящие в интервал [23;31] (выключая границы).

12 Вариант:

Для вычетов 41; 411 по модулю 9:

1. Определим классы, в которые входят данные в условии вычеты (целые числа). Для этого разделим их с остатком на 9, получим:

41 = 9*(4) + 5, значит, 41 принадлежит классу [5]₉;

411 принадлежит классу [6]₉.

2.1. Найдём наименьшие по абсолютной величине вычеты:

m = 9, значит, считаем по формуле для нечётного m:

–(m−1)/2 ≤ x ≤ (m−1)/2

–(9−1)/2 ≤ x ≤ (9−1)/2

–4 ≤ x ≤ 4

2.2. Найдём наименьшие неотрицательные вычеты:

….. -13, -4, 5, 14, 23, 32…..

….. -12, -3, 6, 15, 24, 33 …..

2.3. Найдём вычеты, входящие в интервал [23 ; 31] (выключая границы)

….. -13, -4, 5, 14, 23, 32…..

….. -11, -3, 6, 15, 24, 33 …..

Ответы на 12 Вариант:

[5]₉; [6]₉
-4 ; 4
5 ; 6

5 Вариант:

Для вычетов 34; -54 по модулю 9:

34 = 9*(3) + 7, значит, 34 принадлежит классу [7]₉;

-54 = 9*(-6), значит, -54 принадлежит классу [0]₉.