Теорема Эйлера

В теории чисел , теорема Эйлера (также известный как теорема Ферма-Эйлера или Эйлера totient теорема ) утверждает , что если п и являются взаимно простыми положительными целыми числами, то , возведенное в силе totient из п конгруэнтно к одному, по модулю п , или же:

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

где - функция Эйлера . В 1736 году, Leonhard Euler опубликовал свое доказательство малой теоремы Ферма , ^[1] , который Ферма был представлен без доказательства. Впоследствии Эйлер представил другие доказательства этой теоремы, кульминацией которых стала «теорема Эйлера» в его статье 1763 года, в которой он попытался найти наименьший показатель степени, для которого малая теорема Ферма всегда верна. ^[2]${\displaystyle \varphi (n)}$

Обратные теоремы Эйлера также верно: если выше сравнение верно, то и должен быть взаимно прост.${\displaystyle a}$${\displaystyle n}$

Теорема является обобщением малой теоремы Ферма и далее обобщается теоремой Кармайкла .

Теорема может быть использована для простого уменьшения больших степеней по модулю . Например, рассмотреть вопрос о нахождении них место десятичной цифры , то есть . Целые числа 7 и 10 взаимно просты, и . Итак, теорема Эйлера дает , и мы получаем .${\displaystyle n}$${\displaystyle 7^{222}}$${\displaystyle 7^{222}{\pmod {10}}}$${\displaystyle \varphi (10)=4}$${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$${\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}}$

В общем, при уменьшении степени по модулю (где и взаимно просты) нужно работать по модулю в экспоненте :${\displaystyle a}$${\displaystyle n}$${\displaystyle a}$${\displaystyle n}$${\displaystyle \varphi (n)}$${\displaystyle a}$

если , то .${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$${\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}$

Теорема Эйлера лежит в основе криптосистемы RSA , широко используемой в Интернет- коммуникациях. В этой криптосистеме используется теорема Эйлера, где n является произведением двух больших простых чисел , а безопасность системы основана на сложности факторизации такого целого числа.

Доказательства [ править ]

1. Теорема Эйлера может быть доказана с использованием понятий теории групп : ^[3] Классы вычетов по модулю n , взаимно простые с n, образуют группу при умножении (подробности см. В статье « Мультипликативная группа целых чисел по модулю n» ). Порядок этой группы φ ( п ) . Теорема Лагранжа утверждает, что порядок любой подгруппы конечной группы делит порядок всей группы, в данном случае φ ( n ) . Если a - любое число, взаимно простое сn, то a принадлежит одному из этих классов вычетов, и его степени a , a ² , ..., a ^k по модулю n образуют подгруппу группы классов вычетов с a ^k ≡ 1 (mod n ) . Теорема Лагранжа гласит, что k должно делить φ ( n ) , т.е. существует целое число M такое, что kM = φ ( n ) . Это означает, что

${\displaystyle a^{\varphi (n)}=a^{kM}=(a^{k})^{M}\equiv 1^{M}=1\equiv 1{\pmod {n}}.}$

2. Существует также прямое доказательство: ^{[4] [5]} Пусть R = { x ₁ , x ₂ , ..., x _{φ ( n )} } - приведенная система вычетов ( mod n ) и пусть a - любое целое число взаимно простое с п . Доказательство основано на фундаментальном факте, что умножение на a переставляет x _i : другими словами, если ax _j ≡ ax _k (mod n ), то j = k. (Этот закон сокращения доказан в статье Мультипликативная группа целых чисел по модулю n . ^[6] ) То есть множества R и aR = { ax ₁ , ax ₂ , ..., ax _{φ ( n )} } , рассматриваемые как наборы классов конгруэнтности ( mod n ) идентичны (как наборы - они могут быть перечислены в разном порядке), поэтому произведение всех чисел в R конгруэнтно ( mod n ) произведению всех чисел в aR :

${\displaystyle \prod _{i=1}^{\varphi (n)}x_{i}\equiv \prod _{i=1}^{\varphi (n)}ax_{i}=a^{\varphi (n)}\prod _{i=1}^{\varphi (n)}x_{i}{\pmod {n}},}$и использование закона сокращения для отмены каждого x _i дает теорему Эйлера:

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}.}$

Частное Эйлера [ править ]

Эйлера фактор целого числа а по отношению к п определяется следующим образом:

${\displaystyle q_{n}(a)={\frac {a^{\varphi (n)}-1}{n}}}$

Частный случай фактора Эйлера, когда n простое, называется фактором Ферма .

Любое нечетное число n, которое делится , называется числом Вифериха . Это равносильно утверждению, что 2 ^{φ ( n )} ≡ 1 (mod n ² ). В качестве обобщения, любое число n , которое взаимно просто с положительным целым числом a и такое, что n делится , называется (обобщенным) числом Вифериха для основания a . Это равносильно утверждению, что a ^{φ ( n )} ≡ 1 (mod n ² ). ${\displaystyle q_{n}(2)}$${\displaystyle q_{n}(a)}$

а	числа n, взаимно простые с a, которые делят (найдено до 1048576)${\displaystyle q_{n}(a)}$	Последовательность OEIS
1	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, ... (все натуральные числа)	A000027
2	1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, 473985, 684645, 89516 1232361, 2053935, 2685501, 3697083, 3837523, 6161805, 11512569, ...	A077816
3	1, 11, 22, 44, 55, 110, 220, 440, 880, 1006003, 2012006, 4024012, 11066033, 22132066, 44264132, 55330165, 88528264, 110660330, 221320660, 442641320, 885282640, 177056516280, 11244900 .	A242958
4	1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, 473985, 684645, 89516 ...
5	1, 2, 20771, 40487, 41542, 80974, 83084, 161948, 643901, 1255097, 1287802, 1391657, 1931703, 2510194, 2575604, 2783314, 3765291, 3863406, 4174971, 5020388, 515120830, 7512534, 7712534, 772325 10040776, 11133256, 15061164, 15308227, 15453624, 16699884, ...	A242959
6	1, 66161, 330805, 534851, 2674255, 3152573, 10162169, 13371275, 50810845, 54715147, 129255493, 148170931, 254054225, 273575735, 301121113, 383006029, 646277465, ...	A241978
7	1, 4, 5, 10, 20, 40, 80, 491531, 983062, 1966124, 2457655, 3932248, 4915310, 6389903, 9339089, 9830620, 12288275, 12779806, 18678178, 19169709, 19661240, 24576550, 25559612, ...	A242960
8	1, 3, 1093, 3279, 3511, 7651, 9837, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 206577, 228215, 284391, 298389, 383643, 410787, 473985, 684645, 895167, ...
9	1, 2, 4, 11, 22, 44, 55, 88, 110, 220, 440, 880, 1760, 1006003, ...
10	1, 3, 487, 1461, 4383, 13149, 39447, 118341, 355023, 56598313, 169794939, 509384817, ...	A241977
11	1, 71, 142, 284, 355, 497, 710, 994, 1420, 1491, 1988, 2485, 2840, 2982, 3976, 4970, 5680, 5964, 7455, 9940, 11928, 14910, 19880, 23856, 29820, 39760, 59640, 79520, 119280, 238560, 477120, ...	A253016
12	1, 2693, 123653, 1812389, 2349407, 12686723, 201183431, 332997529, ...	A245529
13	1, 2, 863, 1726, 3452, 371953, 743906, 1487812, 1747591, 1859765, 2975624, 3495182, 3719530, 5242773, 6990364, 7439060, 8737955, 10485546, 14878120, 15993979, 1747592910, 266240810, 201379810, 201379810 34951820, 41942184, 47981937, 52427730, 59512480, ...	A257660
14	1, 29, 353, 3883, 10237, 19415, 112607, 563035, ...
15	1, 4, 8, 29131, 58262, 116524, 233048, 466096, ...
16	1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, 473985, 684645, 89516 ...
17	1, 2, 3, 4, 6, 8, 12, 24, 48, 46021, 48947, 92042, 97894, 138063, 146841, 184084, 195788, 230105, 276126, 293682, 368168, 391576, 414189, 460210, 552252, 587364, 598273, 690315, 736336, 783152, 828378, 920420, ...
18	1, 5, 7, 35, 37, 49, 185, 245, 259, 331, 1295, 1655, 1813, 2317, 3641, 8275, 9065, 11585, 12247, 16219, 18205, 25487, 33923, 57925, 61235, 81095, 85729, 91025, 127435, 134717, 169615, 178409, 237461, 306175, 405475, 428645, 455125, 600103, 637175, 673585, 892045, 943019, ...
19	1, 3, 6, 7, 12, 13, 14, 21, 26, 28, 39, 42, 43, 49, 52, 63, 78, 84, 86, 91, 98, 104, 117, 126, 129, 137, 147, 156, 168, 172, 182, 196, 234, 252, 258, 273, 274, 294, 301, 312, 364, 387, 411, 441, 468, 504, 516, 546, 548, 559, 588, 602, 624, 637, 728, 774, 819, 822, 882, 903, 936, 959, 1032, 1092, 1096, 1118, 1176, 1204, 1274, 1456, 1548, 1638, 1644, 1677, 1764, 1781, 1806, 1872, 1911, 1918, 2107, 2184, 2192, 2236, 2329, 2408, 2457, 2548, 2709, 2877, 3096, 3276, 3288, 3354, 3528, 3562, 3612, 3822, 3836, 3913, 4214, 4368, 4472, 4658, 4914, 5031, 5096, 5343, 5418, 5733, 5754, 5891, 6321, 6552, 6576, 6708, 6713, 6987, 7124, 7224, 7644, 7672, 7826, 8127, 8428, 8631, 8736, 8944, 9316, 9828, 10062, 10192, 10686, 10836, 11466, 11508, 11739, 11782, 12467, 12642, 13104, 13152, 13416, 13426, 13974, 14248, 14448, 14749, 15093, 15288, 15344, 15652, 16029, 16254,16303, 16856, 17199, 17262, 17673, 18632, 18963, 19656, 20124, 20139, 21372, 21672, 22932, 23016, 23478, 23564, 24934, 25284, 26208, 26832, 26852, 27391, 27948, 28496, 29498, 30186, 30277, 30576, 30688, 31304, 32058, 32508, 32606, 34398, 34524, 35217, 35346, 37264, 37401, 37926, 39312, 40248, 40278, 41237, 42744, 43344, 44247, 45864, 46095, 4695 47128, 48909, 49868, 50568, 53019, 53664, 53704, 54782, 55896, 56889, 56992, 58996, 60372, 60417, 60554, 61152, 62608, 64116, 65016, 65212, 68796, 69048, 70434, 7028, 7692 74802, 75852, 76583, 78624, 80496, 80556, 82173, 82474, 85488, 87269, 88494, 90831, 91728, 92064, 93912, 94256, 97818, 99736, 100147, 101136, 105651, 106038, 1074081792, 109564, 112203, 113778, 113984, 114121, 117992, 120744, 120834, 121108, 123711, 125216, 128232, 130032, 130424, 132741, 137592, 138096, 140868, 141384, 146727,149056, 149604, 151704, 153166, 160992, 161112, 164346, 164948, 170976, 174538, 176988, 181662, 183456, 184128, 187824, 188512, 191737, 195636, 199472, 200294, 211302, 211239816, 2120976, 2120976 223584, 224406, 227556, 228242, 229749, 241488, 241668, 242216, 246519, 247422, 256464, 260848, 261807, 265482, 272493, 275184, 276192, 281736, 282768, 288659, 293454, 30140840, 30044 306332, 316953, 322224, 328692, 329896, 336609, 341952, 342363, 349076, 353976, 363324, 371133, 375648, 383474, 391272, 398223, 398944, 400588, 422604, 423878, 424152, 43851, 451288, 447 456484, 459498, 482976, 483336, 484432, 493038, 494844, 512928, 521696, 523614, 530964, 536081, 544986, 550368, 552384, 563472, 565536, 575211, 577318, 586908, 596224, 598412690690, 6908, 6908 635817, 644448, 657384, 659792, 673218, 683904, 684726,689247, 698152, 701029, 707952, 726648, 739557, 742266, 751296, 766948, 782544, 785421, 796446, 797888, 801176, 845208, 847756, 848304, 865977, 876512, 894336, 932186999 966672, 968864, 986076, 989688, 1025856, 1027089, 1043392, 1047228, ...
20	1, 281, 1967, 5901, 46457, ...
21 год	1, 2, ...
22	1, 13, 39, 673, 2019, 4711, 8749, 14133, 26247, 42399, 61243, 78741, 183729, 551187, ...
23	1, 4, 13, 26, 39, 52, 78, 104, 156, 208, 312, 624, 1248, ...
24	1, 5, 25633, 128165, ...
25	1, 2, 4, 20771, 40487, 41542, 80974, 83084, 161948, 166168, 323896, 643901, ...
26 год	1, 3, 5, 9, 15, 45, 71, 213, 355, 497, 639, 1065, 1491, 1775, 2485, 3195, 4473, 5325, 7455, 12425, 13419, 15975, 22365, 37275, 67095, 111825, 335475, ...
27	1, 11, 22, 44, 55, 110, 220, 440, 880, 1006003, ...
28 год	1, 3, 9, 19, 23, 57, 69, 171, 207, 253, 437, 513, 759, 1265, 1311, 1539, 2277, 3795, 3933, 4807, 11385, 11799, 14421, 24035, 35397, 43263, 72105, 129789, 216315, 389367, 648945, ...
29	1, 2, ...
30	1, 7, 160541, ...

Мере базовые б > 1 , который п представляет собой число Wieferich является

2, 5, 8, 7, 7, 17, 18, 15, 26, 7, 3, 17, 19, 19, 26, 31, 38, 53, 28, 7, 19, 3, 28, 17, 57, 19, 80, 19, 14, 107, 115, 63, 118, 65, 18, 53, 18, 69, 19, 7, 51, 19, 19, 3, 26, 63, 53, 17, 18, 57, ... (последовательность A250206 в OEIS )

См. Также [ править ]

• Функция Кармайкла
• Критерий Эйлера
• Маленькая теорема Ферма
• Теорема Вильсона

Заметки [ править ]

Ссылки [ править ]

Disquisitiones Arithmeticae был переведен из Гаусса Цицерона латинского на английский и немецкий языки. Немецкое издание включает все его работы по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих; Кларк, Артур А. (перевод на английский) (1986), Disquisitiones Arithemeticae (второе, исправленное издание) , Нью-Йорк: Springer , ISBN 0-387-96254-9
• Гаусс, Карл Фридрих; Мазер, Х. (перевод на немецкий) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) (второе издание) , Нью-Йорк: Челси, ISBN 0-8284-0191-8
• Харди, GH; Райт, EM (1980), Введение в теорию чисел (пятое издание) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе издание) , Нью-Йорк: Springer , ISBN 0-387-97329-X
• Ландау, Эдмунд (1966), элементарная теория чисел , Нью-Йорк: Челси

Внешние ссылки [ править ]

• Вайсштейн, Эрик У. "Теорема Тотиента Эйлера" . MathWorld .
• Теорема Эйлера-Ферма в PlanetMath