Свойства и вычисление функции Эйлера

Функция Эйлера от натурального n есть количество чисел, меньших n и взаимно простых с n (число 1 взаимно просто с любым числом). При этом считается, что .

Если мы попробуем просто проверять все числа, меньшие n, на взаимную простоту с n, то при больших n программа будет работать часами, а то и сутками. Попробуем посмотреть на задачу внимательнее. Первое, что мы заметим – это то, что простое число всегда взаимно просто со всеми числами, меньше себя, значит, для простых n,

. (1)

Такая операция гораздо легче, чем производить перебор. Далее можно рассмотреть случай, когда n имеет единственный простой делитель p, повторенный несколько раз, т.е. (случай, рассмотренный выше, есть частный случай данного, при k=1). Очевидно, что такое число будет взаимно просто со всеми числами, меньше себя, кроме чисел, кратных p. Всего таких чисел .

Таким образом, мы можем обобщить выражение (1) для простых p:

. (2)

Заметим еще, что, если некоторые числа p и q взаимно просты, то число pq будет взаимно просто со всеми числами, меньшими себя, кроме тех, которые кратны хотя бы одному делителю p или хотя бы одному делителю q. Отсюда имеем еще одно свойство функции Эйлера, а именно: для взаимно простых p и q:

. (3)

Предположим, что мы разложили n на простые множители и записали в каноническом виде: , где все p_i различные простые числа. Тогда, применив (2) и (3), получаем, что при , где p простые числа,

. (4)

ПРИЛОЖЕНИЕ

Таблица П.1. Ключевые слова

Таблица П.2. Цифровой алфавит русского языка

№ варианта	Ключевое слово
1	автопилот
2	монография
3	стабилизатор
4	интегратор
5	синхронизация
6	симфония
7	кабриолет
8	субстанция
9	пиктограмма
10	стробирование
11	факториал
12	комбинация
13	олимпиец
14	стадион
15	футбольный
16	небесный
17	фальшивый
18	интересный
19	чудесный
20	гениальный
21	подиум
22	асимптота
23	гиперболоид
24	сенсационный
25	антикварный
26	рубиновый
27	строптивый
28	коллинеарный
29	криптография
30	абстракция
31	каллиграфия
32	бумеранг
33	аллигатор
34	топография
35	верстка
36	синхрофазотрон
37	клистрон
38	тиристор
39	магнетрон
40	пиктограмма

Буква	Условный №
А	1
Б	2
В	3
Г	4
Д	5
Е, Ё	6
Ж	7
З	8
И, Й	9
К	10
Л	11
М	12
Н	13
О	14
П	15
Р	16
С	17
Т	18
У	19
Ф	20
Х	21
Ц	22
Ч	23
Ш	24
Щ	25
Ъ, Ь	26
Ы	27
Э	28
Ю	29
Я	30
пробел	31

П РИЛОЖЕНИЕ

				Таблица П.4. Варианты к заданию № 2
№	p	q	a	К Р И П Т О Г Р А М М А
1	13	3	7	1	11	16	9	10	14	17	14	3	27	9	34	17	14	10
2	23	3	3	58	9	8	53	14	27	53	56	52	58	1	56	52	56	53	3	53	3
3	11	7	13	73	49	11	62	41	49	58	26	3	12	62	26	41	48	58
4	3	17	3	4	1	25	31	1	7	15	45	12	12	18	7	13	15	18	15	31	25
5	2	19	7	23	29	18	28	6	36	1	11	31	34	22	29	18	19	36	29	27	23
6	13	7	11	23	1	58	76	74	1	47	19	58	1	47	85	14	47	38	14	74	22
7	3	17	5	17	49	36	29	17	18	1	18	46	26	1	18	1	42	44	17	30
8	11	5	11	21	1	23	6	11	6	14	2	31	52	6	11	6	2	38	9
9	7	19	5	78	121	105	100	1	66	87	103	117	110	1	66	4	1	37	1
10	5	11	9	25	4	11	49	28	4	12	16	11	46	52	1	28	20	31	1
11	17	2	7	18	16	19	30	6	21	23	11	14	3	19	22	19	19
12	5	13	7	43	1	50	45	9	16	21	62	59	60	46	43	52	53	9
13	5	7	5	9	1	17	32	4	23	26	23	24	11	6	22	5	4	4
14	19	2	11	14	32	8	34	1	18	27	34	1	18	26	21	26
15	5	19	7	43	37	36	79	33	1	31	2	66	67	37	4	11	30	78	4	4
16	5	11	7	18	36	9	7	2	1	26	25	9	36	9	49	1	35
17	11	7	3	76	27	1	41	57	36	22	20	69	6	15	49	27	41	50
18	2	23	9	7	1	20	41	44	38	15	9	20	44	15	1	3	13	25
19	3	17	11	44	29	15	13	1	16	30	10	22	37	44	17	1
20	13	5	7	38	52	14	58	9	47	46	41	26	21	10	16	14	52	46	10	46	16	1
21	11	7	7	28	41	11	1	62	62	69	37	59	60	42	52	39	5
22	31	2	7	23	41	13	50	40	41	8	7	6	24	15	41	31	23	13	1	53	6	8
23	13	5	5	14	62	18	61	14	62	9	37	41	18	13	27	29	31	50	29	46	26	12
24	7	5	5	15	14	4	12	5	14	33	27	6	26	10	1	13	13	27	6
25	19	3	5	49	24	26	24	50	52	29	24	46	1	26	54	32	54
26	2	23	3	18	39	33	2	30	43	39	6	29	35	1	36	2	39	44
27	11	7	7	52	62	41	28	62	1	2	59	11	1	31	37	62	1
28	3	29	3	47	7	3	47	22	47	7	75	33	7	47	27	1	22	22	21	33
29	5	11	3	8	14	49	26	14	2	23	36	12	51	11	49	27	51	10	1
30	23	2	3	34	27	1	33	2	1	36	5	2	35	41	39	29	37	39	18	35	1	43
31	3	23	5	24	48	5	48	44	16	48	5	38	36	12	60	16	36	48	3	38	19
32	11	13	11	13	50	14	46	27	43	13	14	113	50	13	13	27	42	86	110	63	56
33	13	5	5	62	41	46	29	30	14	13	14	48	1	10	31	5	14	46	29	13	1
34	7	5	5	33	6	16	4	5	14	16	6	15	13	27	4	26	23	14	12	23
35	19	3	5	44	54	55	52	1	26	46	54	52	18	24	55	4	54	4	29	15	1	52
36	2	23	3	17	30	43	44	2	35	41	39	29	33	39	10	43	32	34	36	2	39	34
37	11	7	7	11	1	57	41	58	62	1	2	59	68	52	39	1	62	42	31	10	1
38	3	29	3	64	33	69	42	7	64	42	47	75	42	3	7	33	74	42	41	43	1	30
39	5	11	3	20	18	14	21	49	2	26	49	52	52	49	51	36	49	26	39	13	14	51
40	23	3	5	4	1	44	3	34	30	54	5	16	19	38	5	38	19	36	54	34	18

ПРИЛОЖЕНИЕ

№		R	S
Преподаватель		187	23
Студенты
№	p_i	q_i		s_i
1	2	19		7
2	7	11		11
3	3	17		7
4	3	23		3
5	13	7		5
6	13	3		5
7	11	7		11
8	5	11		9
9	11	7		13
10	11	5		3
11	7	13		5
12	5	7		5
13	5	19		5
14	19	2		11
15	5	11		7
16	17	7		7
17	3	23		3
18	7	17		7
19	13	5		7
20	19	3		5
21	23	7		7
22	19	5		5
23	7	11		7
24	19	5		5
25	3	23		5
26	11	7		11
27	3	29		5
28	3	11		3
29	23	3		3
30	3	23		5
31	11	13		11
32	13	7		5
33	7	7		7
34	17	3		5
35	3	21		3
36	19	7		7
37	5	19		5
38	5	13		5
39	13	7		5
40	29	3		5

Таблица П.5. Варианты задания № 3

Таблица П.6. Простые числа

Простые числа
2	3	5	7	11
13	17	19	23	29
31	37	41	43	47
53	59	61	67	71
73	79	83	89	97
101	103	107	109	113
127	131	137	139	149
151	157	163	167	173
179	181	191	193	197
199	211	223	227	229
233	239	241	251	257
263	269	271	227	281
283	293	307	311	313
317	331	337	347	349

<<< < Предыдущая 1 2 34 / 44

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
10.12.201865.7 Кб6Зад_2_Пастухова_ Мария.docx
#
10.12.201836.24 Кб0Зад_4_Пастухова_Мария.docx
#
13.11.20191.21 Mб7ЗАДА_Б_О.DOC
#
23.09.2019130.05 Кб0задание 3 к семинару по ПСЛ.doc
#
18.04.20191.1 Mб1Задание курсового проекта.doc
#
25.09.2019974.85 Кб1Задание на контрольную работу ИБиЗИ.doc
#
07.07.201924.2 Кб1Задание по тексту.Трансфигурация..docx
#
31.07.201923.2 Кб0задание с1-с4.docx
#
15.04.201555.3 Кб13ЗАДАНИЕ станиславский.doc
#
21.03.201624.88 Кб9задание.docx теплофизика.docx
#
05.12.2018302.08 Кб1Задание_коммуникационные стратегии.doc