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

kjer je 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 in 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 . Recimo da iščemo prvo števko z desne števila , torej . Števili 7 in 10 sta si tuji, velja pa tudi . Torej Eulerjev izrek pokaže , Tako dobimo .

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

če , potem .

DokaziUredi

1. Eulerjev izrek se lahko dokaže z uporabo teorije grup:[3] 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, a2, ... , ak modula n pa izoblikujejo podgrupo grupe razredov ostankov, z ak ≡ 1 (mod n). Lagrangeev izrek pravi, da mora k deliti φ(n), torej obstaja celo število M, da velja kM = φ(n). Iz tega sledi

 

2. Obstaja tudi neposredni dokaz:[4][5] Naj bo R = {x1, x2, ... , 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 xi: z drugimi besedami, če velja axjaxk (mod n), potem j = k. (Ta zakon razveljavitve je dokazan v članku Multiplikativna grupa celih števil modula n.[6]) Torej sta dve množici R in aR = {ax1, ax2, ... , 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:

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

Eulerjev kvocientUredi

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

 

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

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

a števila n, ki so tuja z a, ki delijo   (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, ... (zaporedje A250206 v OEIS)

Glej tudiUredi

OpombeUredi

  1. Glej:
  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,  , 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"
  3. Ireland & Rosen, corr. 1 to prop 3.3.2
  4. Hardy & Wright, thm. 72
  5. Landau, thm. 75
  6. Glej Bézoutova lema

SkliciUredi

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 povezaveUredi