Теорема Эйлера - Eulers theorem

Эта статья посвящена теореме Эйлера в теории чисел. Для использования в других целях см. Список тем имени Леонарда Эйлера.

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

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

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

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

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

Теорема может быть использована для простого уменьшения больших степеней по модулю ${\displaystyle n}$. Например, подумайте о том, чтобы найти единственную десятичную цифру ${\displaystyle 7^{222}}$, т.е. ${\displaystyle 7^{222}{\pmod {10}}}$. Целые числа 7 и 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, который широко используется в Интернет коммуникации. В этой криптосистеме теорема Эйлера используется с п будучи продуктом двух больших простые числа, а безопасность системы основана на сложности факторинг такое целое число.

Доказательства

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

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

2. Также есть прямое доказательство:^[4][5] Позволять р = {Икс₁, Икс₂, ... , Икс_φ(п)} быть система пониженного остатка (мод п) и разреши а быть любым целым числом, взаимно простым с п. Доказательство опирается на фундаментальный факт, что умножение на а переставляет Икс_я: другими словами, если топор_j ≡ топор_k (мод п) тогда j = k. (Этот закон отмены доказан в статье Мультипликативная группа целых чисел по модулю п.^[6]) То есть множества р и aR = {топор₁, топор₂, ... , топор_φ(п)}, рассматриваемые как множества классов конгруэнции (мод п), идентичны (как наборы - они могут быть перечислены в разном порядке), поэтому произведение всех чисел в р конгруэнтно (мод п) к произведению всех чисел в 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}},}$ и используя закон об отмене, чтобы отменить каждый Икс_я дает теорему Эйлера:

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

Фактор Эйлера

В Фактор Эйлера целого числа а относительно п определяется как:

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

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

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

а	числа п взаимно простой с а это деление ${\displaystyle q_{n}(a)}$ (разыскано до 1048576)	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, 895167, 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, 1770565280, 56224501667, 112449003334, ...	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, 895167, ...
5	1, 2, 20771, 40487, 41542, 80974, 83084, 161948, 643901, 1255097, 1287802, 1391657, 1931703, 2510194, 2575604, 2783314, 3765291, 3863406, 4174971, 5020388, 5151208, 5566628, 7530582, 7726812, 8349942, 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, 17475910, 20971092, 26213865, 29756240, 31987958, 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, 895167, ...
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, 46032, 46956, 47128, 48909, 49868, 50568, 53019, 53664, 53704, 54782, 55896, 56889, 56992, 58996, 60372, 60417, 60554, 61152, 62608, 64116, 65016, 65212, 68796, 69048, 70434, 70692, 74528, 74802, 75852, 76583, 78624, 80496, 80556, 82173, 82474, 85488, 87269, 88494, 90831, 91728, 92064, 93912, 94256, 97818, 99736, 100147, 101136, 105651, 106038, 107408, 109564, 111792, 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, 211939, 212076, 214816, 219128, 223584, 224406, 227556, 228242, 229749, 241488, 241668, 242216, 246519, 247422, 256464, 260848, 261807, 265482, 272493, 275184, 276192, 281736, 282768, 288659, 293454, 298112, 299208, 300441, 303408, 306332, 316953, 322224, 328692, 329896, 336609, 341952, 342363, 349076, 353976, 363324, 371133, 375648, 383474, 391272, 398223, 398944, 400588, 422604, 423878, 424152, 438256, 447168, 448812, 455112, 456484, 459498, 482976, 483336, 484432, 493038, 494844, 512928, 521696, 523614, 530964, 536081, 544986, 550368, 552384, 563472, 565536, 575211, 577318, 586908, 596224, 598416, 600882, 612664, 633906, 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, 897624, 901323, 910224, 912968, 918996, 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 который п число Вифериха

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 )

Смотрите также

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

Примечания

1. Видеть:
   • Леонард Эйлер (представлен: 2 августа 1736 г .; опубликован: в 1741 г.) "Теорематум кворундам до нумераса первоисточника спектантиума демонстрация" (Доказательство некоторых теорем о простых числах), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.
   • Для получения дополнительных сведений об этой статье, включая перевод на английский язык, см .: Эйлеров архив.
2. Видеть:
   • Л. Эйлер (опубликовано: 1763 г.) "Теорема арифметики новая методика демонстрации" (Доказательство нового метода в теории арифметики), Новые комментарии academiae scientiarum Petropolitanae, 8 : 74–104. Теорема Эйлера представлена ​​как «Теорема 11» на странице 102. Эта статья была впервые представлена ​​Берлинской академии 8 июня 1758 года и Санкт-Петербургской академии 15 октября 1759 года. В этой статье общая функция Эйлера, ${\displaystyle \varphi (n)}$, не называется, но упоминается как "numerus partium ad N primarum »(количество частей, простых с N; то есть количество натуральных чисел, меньших, чем N и относительно проста с N).
   • Для получения дополнительных сведений об этой статье см .: Эйлеров архив.
   • Для обзора работы Эйлера за годы, приведшие к теореме Эйлера, см .: Эд Сандифер (2005) "Доказательство Эйлера малой теоремы Ферма"
3. Ирландия и Розен, корр. 1 к опоре 3.3.2
4. Харди и Райт, thm. 72
5. Ландау, thm. 75
6. Видеть Лемма Безу

Рекомендации

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

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

внешняя ссылка

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