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^{φ (n)} \equiv 1 (\mod n)

kjer je $φ (n)$ Eulerjeva funkcija fi. (Zapis je opisan v članku.) Leta 1736 je Leonhard Euler objavil svoj dokaz Fermatovega malega izreka,^[1] 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.^[2]

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} (\mod 10)$ . Števili 7 in 10 sta si tuji, velja pa tudi $φ (10) = 4$ . Torej Eulerjev izrek pokaže $7^{4} \equiv 1 (\mod 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 (\mod 10)$ .

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

če

x \equiv y (\mod φ (n))

, potem

a^{x} \equiv a^{y} (\mod n)

.

Dokazi

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

a^{φ (n)} = a^{k M} = (a^{k})^{M} \equiv 1^{M} = 1 \equiv 1 (\mod n) .

2. Obstaja tudi neposredni dokaz:^[4]^[5] Naj bo Predloga:Matematična formula zmanjšani razred ostankov (Predloga:Matematična formula) in naj bo Predloga:Mvar katerokoli celo število, ki je tuje z Predloga:Mvar. Dokaz se oklepa osnovnega dejstva, da množenje z Predloga:Mvar permutira Predloga:Mvar: z drugimi besedami, če velja Predloga:Matematična formula, potem Predloga:Matematična formula. (Ta zakon razveljavitve je dokazan v članku Multiplikativna grupa celih števil modula n.^[6]) Torej sta dve množici Predloga:Mvar in Predloga:Matematična formula, ki se obravnavata kot množici kongruenčnih razredov (Predloga:Matematična formula), identični (kot množici—lahko se zapišeta v drugačnem vrstnem redu), torej je zmnožek vseh števil iz Predloga:Mvar kongruenten (Predloga:Matematična formula) zmnožku vseh števil v Predloga:Mvar:

\prod_{i = 1}^{φ (n)} x_{i} \equiv \prod_{i = 1}^{φ (n)} a x_{i} = a^{φ (n)} \prod_{i = 1}^{φ (n)} x_{i} (\mod n),

tako z uporabo zakona o razveljavitvi za razveljavitev vsakega Predloga:Mvar dobimo Eulerjev izrek:

a^{φ (n)} \equiv 1 (\mod n) .

Eulerjev kvocient

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

q_{n} (a) = \frac{a^{φ (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)	Predloga:OEIS link
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, ...	Predloga:OEIS link
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, ...	Predloga:OEIS link
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, ...	Predloga:OEIS link
6	1, 66161, 330805, 534851, 2674255, 3152573, 10162169, 13371275, 50810845, 54715147, 129255493, 148170931, 254054225, 273575735, 301121113, 383006029, 646277465, ...	Predloga:OEIS link
7	1, 4, 5, 10, 20, 40, 80, 491531, 983062, 1966124, 2457655, 3932248, 4915310, 6389903, 9339089, 9830620, 12288275, 12779806, 18678178, 19169709, 19661240, 24576550, 25559612, ...	Predloga:OEIS link
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, ...	Predloga:OEIS link
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, ...	Predloga:OEIS link
12	1, 2693, 123653, 1812389, 2349407, 12686723, 201183431, 332997529, ...	Predloga:OEIS link
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, ...	Predloga:OEIS link
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, ... Predloga:OEIS

Glej tudi

Opombe

Predloga:Sklici

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.

Zunanje povezave

↑
Glej:
- Leonhard Euler (predstavljeno: 2. avgust 1736; izdano: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Dokaz določenih izrekov o praštevilih), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.
- Za nadaljnje podrobnosti o tem delu, vključno z angleškim prevodom, glej: Eulerjev arhiv.
↑
Glej:
- L. Euler (izdano: 1763) "Theoremata arithmetica nova methodo demonstrata" (Dokaz novega načina v teoriji aritmetike), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Eulerjev izrek se pojavi kot "Theorema 11" na strani 102. To delo je bilo prvič predstavljeno Berlinski akademiji 8. junija 1758 in Sanktpeterburški akademiji 15. oktobra 1759. V tem delu Eulerjeva funkcija fi, $φ (n)$ , ni poimenovana, ampak navedena kot "numerus partium ad N primarum" (število delov praštevila k N; to je število naravnih števil, ki so manjša od N in mu tudi tuja).
- Za več podrobnosti o tem delu, glej: Eulerjev arhiv.
- Za pregled Eulerjevega dela skozi leta, ki so sledila k Eulerjevem izreku, glej: Ed Sandifer (2005) "Eulerjev dokaz Fermatovega malega izreka" Predloga:Webarchive
↑ Ireland & Rosen, corr. 1 to prop 3.3.2
↑ Hardy & Wright, thm. 72
↑ Landau, thm. 75
↑ Glej Bézoutova lema

[1] Glej:
Leonhard Euler (predstavljeno: 2. avgust 1736; izdano: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Dokaz določenih izrekov o praštevilih), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.

Za nadaljnje podrobnosti o tem delu, vključno z angleškim prevodom, glej: Eulerjev arhiv.

[2] Leonhard Euler (predstavljeno: 2. avgust 1736; izdano: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Dokaz določenih izrekov o praštevilih), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.

[3] Za nadaljnje podrobnosti o tem delu, vključno z angleškim prevodom, glej: Eulerjev arhiv.

[2] Glej:
L. Euler (izdano: 1763) "Theoremata arithmetica nova methodo demonstrata" (Dokaz novega načina v teoriji aritmetike), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Eulerjev izrek se pojavi kot "Theorema 11" na strani 102. To delo je bilo prvič predstavljeno Berlinski akademiji 8. junija 1758 in Sanktpeterburški akademiji 15. oktobra 1759. V tem delu Eulerjeva funkcija fi, $φ (n)$ , ni poimenovana, ampak navedena kot "numerus partium ad N primarum" (število delov praštevila k N; to je število naravnih števil, ki so manjša od N in mu tudi tuja).

Za več podrobnosti o tem delu, glej: Eulerjev arhiv.

Za pregled Eulerjevega dela skozi leta, ki so sledila k Eulerjevem izreku, glej: Ed Sandifer (2005) "Eulerjev dokaz Fermatovega malega izreka" Predloga:Webarchive

[5] L. Euler (izdano: 1763) "Theoremata arithmetica nova methodo demonstrata" (Dokaz novega načina v teoriji aritmetike), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Eulerjev izrek se pojavi kot "Theorema 11" na strani 102. To delo je bilo prvič predstavljeno Berlinski akademiji 8. junija 1758 in Sanktpeterburški akademiji 15. oktobra 1759. V tem delu Eulerjeva funkcija fi, $φ (n)$ , ni poimenovana, ampak navedena kot "numerus partium ad N primarum" (število delov praštevila k N; to je število naravnih števil, ki so manjša od N in mu tudi tuja).

[6] Za več podrobnosti o tem delu, glej: Eulerjev arhiv.

[7] Za pregled Eulerjevega dela skozi leta, ki so sledila k Eulerjevem izreku, glej: Ed Sandifer (2005) "Eulerjev dokaz Fermatovega malega izreka" Predloga:Webarchive

[3] Ireland & Rosen, corr. 1 to prop 3.3.2

[4] Hardy & Wright, thm. 72

[5] Landau, thm. 75

[6] Glej Bézoutova lema

[1]

[2]

[3]

[4]

[5]

[6]

Eulerjev izrek

Vsebina

Dokazi

Eulerjev kvocient

Glej tudi

Opombe

Sklici

Zunanje povezave

Navigacijski meni

Eulerjev izrek

Dokazi

Eulerjev kvocient

Glej tudi

Opombe

Sklici

Zunanje povezave

Navigacijski meni

Iskanje