Eulersova věta - Eulers theorem - Wikipedia

v teorie čísel, Eulerova věta (také známý jako Fermat – Eulerova věta nebo Eulerova totientová věta) uvádí, že pokud n a A jsou coprime kladná celá čísla A povýšen na sílu totient z n je shodný s jedním, modulo nnebo

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

kde ${ displaystyle varphi (n)}$ je Eulerova totientová funkce. V roce 1736 Leonhard Euler zveřejnil svůj důkaz o Fermatova malá věta,^[1] který Fermat předložil bez důkazu. Následně Euler předložil další důkazy věty, které vyvrcholily „Eulerovou větou“ ve své práci z roku 1763, ve které se pokusil najít nejmenšího exponenta, pro který Fermatova malá věta vždy platila.^[2]

Rovněž platí obrácení Eulerovy věty: pokud platí výše uvedená shoda, pak ${ displaystyle a}$ a ${ displaystyle n}$ musí být coprime.

Věta je zobecněním Fermatova malá věta, a je dále zobecněna na Carmichaelova věta.

Věta může být použita ke snadné redukci velkých výkonů modulo ${ displaystyle n}$ . Zvažte například nalezení desetinných číslic z těch ${ displaystyle 7 ^ {222}}$ , tj. ${ displaystyle 7 ^ {222} { pmod {10}}}$ . Celá čísla 7 a 10 jsou coprime a ${ displaystyle varphi (10) = 4}$ . Eulerova věta se tedy vzdá ${ displaystyle 7 ^ {4} equiv 1 { pmod {10}}}$ a máme ${ displaystyle 7 ^ {222} equiv 7 ^ {4 krát 55 + 2} equiv (7 ^ {4}) ^ {55} krát 7 ^ {2} equiv 1 ^ {55} krát 7 ^ {2} equiv 49 equiv 9 { pmod {10}}}$ .

Obecně platí, že při snižování výkonu ${ displaystyle a}$ modulo ${ displaystyle n}$ (kde ${ displaystyle a}$ a ${ displaystyle n}$ coprime), je třeba pracovat modulo ${ displaystyle varphi (n)}$ v exponentu ${ displaystyle a}$ :

-li

{ displaystyle x equiv y { pmod { varphi (n)}}}

, pak

{ displaystyle a ^ {x} equiv a ^ {y} { pmod {n}}}

.

Eulerova věta je základem Kryptosystém RSA, který je široce používán v Internet komunikace. V tomto kryptosystému se používá Eulerova věta $n$ být produktem dvou velkých prvočísla a bezpečnost systému je založena na obtížnosti factoring takové celé číslo.

Důkazy

1. Eulerovu větu lze dokázat pomocí konceptů z teorie grup:^[3] Třídy reziduí modulo $n$ které jsou coprime $n$ tvoří skupinu pod násobením (viz článek Multiplikativní skupina celých čísel modulo n pro detaily). The objednat této skupiny je $φ (n)$ . Lagrangeova věta uvádí, že pořadí jakékoli podskupiny a konečná skupina rozdělí pořadí celé skupiny, v tomto případě $φ (n)$ . Li $A$ je libovolné číslo coprime na $n$ pak $A$ je v jedné z těchto tříd reziduí a jejích silách $A, A 2, ... , A k$ modulo $n$ tvoří podskupinu skupiny tříd reziduí s $A k \equiv 1 (mod n)$ . Říká Lagrangeova věta $k$ musí se rozdělit $φ (n)$ , tj. existuje celé číslo $M$ takhle $kM = φ (n)$ . To pak znamená,

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

2. Existuje také přímý důkaz:^[4]^[5] Nechat $R = {X 1, X 2, ... , X φ (n)}$ být systém redukovaných zbytků ( $mod n$ ) a nechte $A$ být jakýkoli celočíselný coprime $n$ . Důkaz závisí na základní skutečnosti, že násobení $A$ permutuje $X i$ : jinými slovy pokud $sekera j \equiv sekera k (mod n)$ pak $j = k$ . (Tento zákon o zrušení je prokázán v článku Multiplikativní skupina celých čísel modulo n.^[6]) To znamená, že sady $R$ a $aR = {sekera 1, sekera 2, ... , sekera φ (n)}$ , považovány za sady tříd shody ( $mod n$ ), jsou identické (jako sady - mohou být uvedeny v různých objednávkách), takže součin všech čísel v $R$ je shodný ( $mod n$ ) na součin všech čísel v $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}},}

a pomocí zákona o zrušení je zrušit každý

X i

dává Eulerovu větu:

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

Eulerův kvocient

The Eulerův kvocient celého čísla A s ohledem na n je definován jako:

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

Zvláštní případ Eulerova kvocientu, když n je prvočíslo se nazývá a Fermatův kvocient.

Jakékoli liché číslo n který rozděluje ${ displaystyle q_ {n} (2)}$ se nazývá a Wieferichovo číslo. To odpovídá tvrzení, že 2^{$φ$ (n)} ≡ 1 (mod n²). Jako zobecnění libovolné číslo n to je coprime na kladné celé číslo A, a tak dále n rozděluje ${ displaystyle q_ {n} (a)}$ , se nazývá (zobecněné) Wieferichovo číslo, které se má založit A. To odpovídá tvrzení, že a^{$φ$ (n)} ≡ 1 (mod n²).

A	čísla n coprime na A to dělí ${ displaystyle q_ {n} (a)}$ (prohledáno až 1048576)	OEIS sekvence
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, ... (všechna přirozená čísla)	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, ...

Nejméně základna b > 1 který n je Wieferichovo číslo

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, ... (sekvence A250206 v OEIS )

Viz také

Poznámky

^
Vidět:
- Leonhard Euler (představen: 2. srpna 1736; publikováno: 1741) „Theorematum quorundam ad numeros primos spectantium demonstratio“ (Důkaz určitých vět o prvočíslech), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.
- Další podrobnosti o tomto příspěvku, včetně anglického překladu, najdete na: Archiv Euler.
^
Vidět:
- L. Euler (publikováno: 1763) „Theoremata arithmetica nova methodo demonstrata“ (Důkaz nové metody v teorii aritmetiky), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Eulerova věta se jeví jako „Theorema 11“ na straně 102. Tento dokument byl poprvé představen berlínské akademii 8. června 1758 a petrohradské akademii 15. října 1759. V tomto článku Eulerova totientní funkce, ${ displaystyle varphi (n)}$ , není pojmenován, ale je označován jako „numerus partium ad N primarum "(počet dílů na N; tj. počet přirozených čísel, který je menší než N a relativně hlavní N).
- Další podrobnosti o tomto příspěvku viz: Archiv Euler.
- Přehled Eulerovy práce za ta léta, která vedla k Eulerově teorému, viz: Ed Sandifer (2005) „Eulerův důkaz Fermatovy malé věty“
^ Irsko a Rosen, kor. 1 k návrhu 3.3.2
^ Hardy & Wright, thm. 72
^ Landau, thm. 75
^ Vidět Bézoutovo lemma

Reference

The Disquisitiones Arithmeticae byl přeložen z Gaussovy ciceronské latiny do angličtiny a němčiny. Německé vydání obsahuje všechny jeho práce o teorii čísel: všechny důkazy kvadratické reciprocity, určení znaménka Gaussovy sumy, vyšetřování biquadratické reciprocity a nepublikované poznámky.

Gauss, Carl Friedrich; Clarke, Arthur A. (přeloženo do angličtiny) (1986), Disquisitiones Arithemeticae (druhé, opravené vydání), New York: Springer, ISBN 0-387-96254-9
Gauss, Carl Friedrich; Maser, H. (přeloženo do němčiny) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae a další články o teorii čísel) (druhé vydání), New York: Chelsea, ISBN 0-8284-0191-8
Hardy, G. H .; Wright, E. M. (1980), Úvod do teorie čísel (páté vydání), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Irsko, Kenneth; Rosen, Michael (1990), Klasický úvod do moderní teorie čísel (druhé vydání), New York: Springer, ISBN 0-387-97329-X
Landau, Edmund (1966), Základní teorie čísel, New York: Chelsea

externí odkazy

[1] Vidět:
Leonhard Euler (představen: 2. srpna 1736; publikováno: 1741) „Theorematum quorundam ad numeros primos spectantium demonstratio“ (Důkaz určitých vět o prvočíslech), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.
Další podrobnosti o tomto příspěvku, včetně anglického překladu, najdete na: Archiv Euler.

[2] Leonhard Euler (představen: 2. srpna 1736; publikováno: 1741) „Theorematum quorundam ad numeros primos spectantium demonstratio“ (Důkaz určitých vět o prvočíslech), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.

[3] Další podrobnosti o tomto příspěvku, včetně anglického překladu, najdete na: Archiv Euler.

[2] Vidět:
L. Euler (publikováno: 1763) „Theoremata arithmetica nova methodo demonstrata“ (Důkaz nové metody v teorii aritmetiky), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Eulerova věta se jeví jako „Theorema 11“ na straně 102. Tento dokument byl poprvé představen berlínské akademii 8. června 1758 a petrohradské akademii 15. října 1759. V tomto článku Eulerova totientní funkce, ${ displaystyle varphi (n)}$ , není pojmenován, ale je označován jako „numerus partium ad N primarum "(počet dílů na N; tj. počet přirozených čísel, který je menší než N a relativně hlavní N).
Další podrobnosti o tomto příspěvku viz: Archiv Euler.
Přehled Eulerovy práce za ta léta, která vedla k Eulerově teorému, viz: Ed Sandifer (2005) „Eulerův důkaz Fermatovy malé věty“

[5] L. Euler (publikováno: 1763) „Theoremata arithmetica nova methodo demonstrata“ (Důkaz nové metody v teorii aritmetiky), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Eulerova věta se jeví jako „Theorema 11“ na straně 102. Tento dokument byl poprvé představen berlínské akademii 8. června 1758 a petrohradské akademii 15. října 1759. V tomto článku Eulerova totientní funkce, ${ displaystyle varphi (n)}$ , není pojmenován, ale je označován jako „numerus partium ad N primarum "(počet dílů na N; tj. počet přirozených čísel, který je menší než N a relativně hlavní N).

[6] Další podrobnosti o tomto příspěvku viz: Archiv Euler.

[7] Přehled Eulerovy práce za ta léta, která vedla k Eulerově teorému, viz: Ed Sandifer (2005) „Eulerův důkaz Fermatovy malé věty“

[3] Irsko a Rosen, kor. 1 k návrhu 3.3.2

[4] Hardy & Wright, thm. 72

[5] Landau, thm. 75

[6] Vidět Bézoutovo lemma

[1]

[2]

[3]

[4]

[5]

[6]