Расчет значения функции Эйлера

Целое положительное число

Функция Эйлера - такая функция от целого положительного числа, значение которой равно количеству натуральных чисел, меньших заданного числа  и взаимно простых с ним.

При этом полагают, что число 1 взаимно просто со всеми натуральными числами.

Если заданное число N является простым то логично предложить что функция Эйлера будет равна N-1, так как все числа меньше N, являются взаимно простыми  к заданному.

Например, значение функции Эйлера числа 33 равно 20. Как такое получилось?

Разложим 33 на множители получим  3*11.  Запомним их и будем сравнивать с рядом чисел от 1 до 32.

Напомним, что  взаимно простыми числами являются таки числа, которые не имеют общих делителей.

Считаем  взаимно простые числа: 1,2 ,3(не учитываем),4,5,6(делится на 3),7,8,9,10,11(делится на 11),12,13,14,15,16,17,18,19,20,21(делится на три),22(делится на 11),23,24,25,26,27,28,29,30,31,32

Посчитаем сколько получилось  зачеркнутых чисел? 

Их 12, ряд чисел содержит  32 элемента ( от 1 до 33) тогда количество не зачёркнутых (взаимно простых) чисел будет 32-12 =20

Есть еще простой способ рассчитывать значения функции

Разложим  произвольное число  например 4832 на простые множители.

Получим  

Функция Эйлера равна 

То есть, если у  вас число N  представлено в виде простых сомножителей вида  

то функция Эйлера будет равна

 

Вот еще пример 

Рассчитаем значение фунции числа 100

тогда значение функции Эйлера равно 

Применимость числа Эйлера в теории чисел и криптографии достаточно велико, но мы будем её использовать для расчета линейных диофантовых уравнений с двумя неизвестными.

Напоследок, представляем таблицу значений функции Эйлера для первых 500 чисел

1	1	101	100	201	132	301	252	401	400
2	1	102	32	202	100	302	150	402	132
3	2	103	102	203	168	303	200	403	360
4	2	104	48	204	64	304	144	404	200
5	4	105	48	205	160	305	240	405	216
6	2	106	52	206	102	306	96	406	168
7	6	107	106	207	132	307	306	407	360
8	4	108	36	208	96	308	120	408	128
9	6	109	108	209	180	309	204	409	408
10	4	110	40	210	48	310	120	410	160
11	10	111	72	211	210	311	310	411	272
12	4	112	48	212	104	312	96	412	204
13	12	113	112	213	140	313	312	413	348
14	6	114	36	214	106	314	156	414	132
15	8	115	88	215	168	315	144	415	328
16	8	116	56	216	72	316	156	416	192
17	16	117	72	217	180	317	316	417	276
18	6	118	58	218	108	318	104	418	180
19	18	119	96	219	144	319	280	419	418
20	8	120	32	220	80	320	128	420	96
21	12	121	110	221	192	321	212	421	420
22	10	122	60	222	72	322	132	422	210
23	22	123	80	223	222	323	288	423	276
24	8	124	60	224	96	324	108	424	208
25	20	125	100	225	120	325	240	425	320
26	12	126	36	226	112	326	162	426	140
27	18	127	126	227	226	327	216	427	360
28	12	128	64	228	72	328	160	428	212
29	28	129	84	229	228	329	276	429	240
30	8	130	48	230	88	330	80	430	168
31	30	131	130	231	120	331	330	431	430
32	16	132	40	232	112	332	164	432	144
33	20	133	108	233	232	333	216	433	432
34	16	134	66	234	72	334	166	434	180
35	24	135	72	235	184	335	264	435	224
36	12	136	64	236	116	336	96	436	216
37	36	137	136	237	156	337	336	437	396
38	18	138	44	238	96	338	156	438	144
39	24	139	138	239	238	339	224	439	438
40	16	140	48	240	64	340	128	440	160
41	40	141	92	241	240	341	300	441	252
42	12	142	70	242	110	342	108	442	192
43	42	143	120	243	162	343	294	443	442
44	20	144	48	244	120	344	168	444	144
45	24	145	112	245	168	345	176	445	352
46	22	146	72	246	80	346	172	446	222
47	46	147	84	247	216	347	346	447	296
48	16	148	72	248	120	348	112	448	192
49	42	149	148	249	164	349	348	449	448
50	20	150	40	250	100	350	120	450	120
51	32	151	150	251	250	351	216	451	400
52	24	152	72	252	72	352	160	452	224
53	52	153	96	253	220	353	352	453	300
54	18	154	60	254	126	354	116	454	226
55	40	155	120	255	128	355	280	455	288
56	24	156	48	256	128	356	176	456	144
57	36	157	156	257	256	357	192	457	456
58	28	158	78	258	84	358	178	458	228
59	58	159	104	259	216	359	358	459	288
60	16	160	64	260	96	360	96	460	176
61	60	161	132	261	168	361	342	461	460
62	30	162	54	262	130	362	180	462	120
63	36	163	162	263	262	363	220	463	462
64	32	164	80	264	80	364	144	464	224
65	48	165	80	265	208	365	288	465	240
66	20	166	82	266	108	366	120	466	232
67	66	167	166	267	176	367	366	467	466
68	32	168	48	268	132	368	176	468	144
69	44	169	156	269	268	369	240	469	396
70	24	170	64	270	72	370	144	470	184
71	70	171	108	271	270	371	312	471	312
72	24	172	84	272	128	372	120	472	232
73	72	173	172	273	144	373	372	473	420
74	36	174	56	274	136	374	160	474	156
75	40	175	120	275	200	375	200	475	360
76	36	176	80	276	88	376	184	476	192
77	60	177	116	277	276	377	336	477	312
78	24	178	88	278	138	378	108	478	238
79	78	179	178	279	180	379	378	479	478
80	32	180	48	280	96	380	144	480	128
81	54	181	180	281	280	381	252	481	432
82	40	182	72	282	92	382	190	482	240
83	82	183	120	283	282	383	382	483	264
84	24	184	88	284	140	384	128	484	220
85	64	185	144	285	144	385	240	485	384
86	42	186	60	286	120	386	192	486	162
87	56	187	160	287	240	387	252	487	486
88	40	188	92	288	96	388	192	488	240
89	88	189	108	289	272	389	388	489	324
90	24	190	72	290	112	390	96	490	168
91	72	191	190	291	192	391	352	491	490
92	44	192	64	292	144	392	168	492	160
93	60	193	192	293	292	393	260	493	448
94	46	194	96	294	84	394	196	494	216
95	72	195	96	295	232	395	312	495	240
96	32	196	84	296	144	396	120	496	240
97	96	197	196	297	180	397	396	497	420
98	42	198	60	298	148	398	198	498	164
99	60	199	198	299	264	399	216	499	498
100	40	200	80	300	80	400	160	500	200

Удачных расчетов!

• << Расчет детерминанта комплексной матрицы
• Расчет квадратного, кубического и 4 степени уравнения онлайн >>