Eulerjev izrek

V teoriji števil Eulerjev izrek [òjlerjev izrek] (znan tudi kot Fermat–Eulerjev izrek ali Eulerjev totientni izrek) pravi, da za tuji si števili n in a velja

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

kjer je $\varphi (n)$ Eulerjeva funkcija fi. (Zapis je opisan v članku.) Leta 1736 je Leonhard Euler objavil svoj dokaz Fermatovega malega izreka, ki ga je že prej brez dokaza predstavil Fermat. Kasneje je Euler objavil tudi ostale dokaze tega izreka, ki so v njegovem delu iz leta 1763 združili v "Eulerjev izrek", kjer je hotel odkriti najmanjši eksponent, za katerega je Fermatov mali izrek vedno pravilen.

Velja tudi obratni Eulerjev izrek: če zgornja kongruenca velja, potem morata biti $a$ in $n$ tuji si števili.

Izrek je posplošitev Fermatovega malega izreka, še bolj pa se posploši s Carmichaelovim izrekom.

Izrek se lahko uporabi za enostavno zmanjševanje velikih potenc modula $n$. Recimo da iščemo prvo števko z desne števila $7^{222}$, torej $7^{222}{\pmod {10}}$. Števili 7 in 10 sta si tuji, velja pa tudi $\varphi (10)=4$. Torej Eulerjev izrek pokaže $7^{4}\equiv 1{\pmod {10}}$, Tako dobimo $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}}$.

Ko zmanjšujemo potenco od $a$ modula $n$ (kjer sta si $a$ in $n$ tuji), se mora v splošnem delati v modulu $\varphi (n)$ na eksponentu od $a$:

če $x\equiv y{\pmod {\varphi (n)}}$, potem $a^{x}\equiv a^{y}{\pmod {n}}$.

Dokazi

1. Eulerjev izrek se lahko dokaže z uporabo teorije grup: Razredi ostankov modula n, ki so si tuji z n, izoblikujejo grupo pod množenjem (glej članek Multiplikativna grupa celih števil modula n za podrobnosti). Red te grupe je φ(n), kjer φ označuje Eulerjevo funkcijo fi. Lagrangov izrek pravi, da red katerekoli podgrupe končne grupe deli rede cele grupe, v tem primeru φ(n). Če je a katerokoli število, ki si je tuje z n, potem je a v enem izmed teh razredov ostankov, njegove potence a, a², ... , a^k modula n pa izoblikujejo podgrupo grupe razredov ostankov, z a^k ≡ 1 (mod n). Lagrangeev izrek pravi, da mora k deliti φ(n), torej obstaja celo število M, da velja kM = φ(n). Iz tega sledi

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

2. Obstaja tudi neposredni dokaz: Naj bo R = {x₁, x₂, ... , x_φ(n)} zmanjšani razred ostankov (mod n) in naj bo a katerokoli celo število, ki je tuje z n. Dokaz se oklepa osnovnega dejstva, da množenje z a permutira x_i: z drugimi besedami, če velja ax_j ≡ ax_k (mod n), potem j = k. (Ta zakon razveljavitve je dokazan v članku Multiplikativna grupa celih števil modula n.) Torej sta dve množici R in aR = {ax₁, ax₂, ... , ax_φ(n)}, ki se obravnavata kot množici kongruenčnih razredov (mod n), identični (kot množici—lahko se zapišeta v drugačnem vrstnem redu), torej je zmnožek vseh števil iz R kongruenten (mod n) zmnožku vseh števil v aR:

$\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}},$ tako z uporabo zakona o razveljavitvi za razveljavitev vsakega x_i dobimo Eulerjev izrek:

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

Eulerjev kvocient

Eulerjev kvocient je celo število a glede na n, ki je definirano kot:

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

Poseben primer Eulerjevega kvocienta pri praštevilu n, se imenuje Fermatov kvocient.

Katerokoli liho število n, ki deli $q_{n}(2)$, se imenuje Wieferichovo število. To je ekvivalentno kongruenci 2^φ(n) ≡ 1 (mod n²). Kot posplošitev, se vsako število n, ki je tuje z naravnim številom a in deli $q_{n}(a)$, se imenuje (posplošeno) Wieferichovo število v osnovi a. To je ekvivalentno kongruenci a^φ(n) ≡ 1 (mod n²).

a	števila n, ki so tuja z a, ki delijo $q_{n}(a)$ (do 1048576)	Zaporedje 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, ... (vsa naravna števila)	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, ...

Najmanjše osnove b > 1, za katere je n Wieferichovo število, so

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

Glej tudi

• Carmichaelova funkcija
• Eulerjev kriterij
• Fermatov mali izrek
• Wilsonov izrek

Sklici

Disquisitiones Arithmeticae je bila prevedena iz Gaussove ciceronske latinščine v angleščino in nemščino. Nemška verzija vsebuje vse njegove zapise o teoriji števil: vse dokaze kvadratne recipročnosti, določitev znaka Gaussovih vsot, raziskovanja bikvadratne recipročnosti in neobjavljene opombe.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translated into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9
• Gauss, Carl Friedrich; Maser, H. (translated into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X
• Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea

Zunanje povezave

• Weisstein, Eric Wolfgang. »Euler's Totient Theorem«. MathWorld.
• Euler-Fermat Theorem na PlanetMath