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

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

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

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

При этом полагают, что число 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 на простые множители.

Получим  Простые множители заданного числа

Функция Эйлера равна (2^{5}-2^{4})*(151^{1}-151^{0}=(32-16)(151-1)=2400

То есть, если у  вас число N  представлено в виде простых сомножителей вида  P_1^{B_1}P_2^{B_2}.....P_m^{B_m}

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

(P_1^{B_1}-P_1^{B_1-1})(P_2^{B_2}-P_2^{B_2-1}).....(P_m^{B_m}-P_m^{B_m-1})

 

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

Рассчитаем значение фунции числа 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

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

Поиск по сайту