Teorema Euler

Dalam teori bilangan, Teorema Euler (juga dikenal sebagai Teorema Fermat-Euler atau Teorema Total Euler) menyatakan bahwa jika n dan a adalah bilangan bulat positif yang saling koprima, maka a pangkat fungsi phi dari n kongruen dengan satu, dalam modulo n, atau:

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

dengan $\varphi (n)$ adalah fungsi phi Euler. Pada tahun 1736, Leonhard Euler mempublikasikan bukti teorema kecil Fermat versinya,^[1] karena Fermat tidak menyertakan bukti teorema tersebut. Selanjutnya, Euler menerbitkan bukti lain dari teorema tersebut, yang berpuncak pada "Teorema Euler" dalam makalahnya tahun 1763, di mana ia mencoba untuk menemukan eksponen terkecil sehinga teorema kecil Fermat selalu bernilai benar.^[2]

Kebalikan dari teorema Euler: jika kekongruenan di atas benar, maka $a$ dan $n$ saling koprima.

Teorema Euler adalah generalisasi dari teorema kecil Fermat, dan dapat digeneralisasikan lebih lanjut dengan teorema Carmichael.

Teorema Euler dapat digunakan untuk mengurangi nilai pangkat yang besar pada modulo $n$ . Misalnya, anggap kita perlu untuk mencari digit desimal tempat satuan dari $7^{222}$ , dengan kata lain, $7^{222}{\pmod {10}}$ . Bilangan bulat 7 dan 10 saling koprima, dan nilai $\varphi (10)=4$ . Selanjutnya, dengan menggunakan teorema Euler didapatkan $7^{4}\equiv 1{\pmod {10}}$ , dan hasil diperoleh adalah $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}}$ .

Secara umum, mengurangi pangkat $a$ pada modulo $n$ (di mana $a$ dan $n$ saling koprima), kita cukup bekerja pada modulo $\varphi (n)$ dalam perpangkatan $a$ :

jika

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

, maka

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

.

Teorema Euler menjadi dasar algoritma RSA, yang banyak digunakan dalam sistem komunikasi di Internet. Dalam algoritma ini, teorema Euler digunakan bersama sebuah bilangan $n$ , yang merupakan hasil kali dari dua bilangan prima besar, dan tingkat keamanan algoritma didasarkan pada tingkat kesulitan untuk memfaktorkan bilangan $n$ tersebut.

Contoh

Untuk $n=p$ prima

a^{p-1}=1{\pmod {p}},

karena $\varphi (p)=p-1$ . Itu Teorema kecil Fermat.

Bukti

Terdapat beberapa cara untuk membuktikan Teorema Euler, berikut dua diantaranya.

Teori grup

Teorema Euler dapat dibuktikan dengan menggunakan konsep dari teori grup:^[3] Kelas residu modulo $n$ yang coprime untuk $n$ membentuk kelompok dalam perkalian (lihat artikel Grup perkalian bilangan bulat modulo $n$ ). urutan dari grup adalah $φ (n)$ . Teorema Lagrange urutan subgrup dari sebuah grup hingga membagi urutan seluruh grup, dalam hal ini $φ (n)$ . Jika $a$ bilangan koprima sampai $n$ maka $a$ salah satu kelas residu, dan pangkat $a, a 2, ... , a k$ modulo $n$ subgrup dari grup kelas residu, dengan $a k \equiv 1 (mod n)$ . Teorema Lagrange mengatakan $k$ harus membagi $φ (n)$ , yaitu bilangan bulat $M$ sedemikian rupa sehingga $kM = φ (n)$ . Ini kemudian menyiratkan,

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

Bukti langsung

Teorema Euler juga dapat dibuktikan secara langsung:^[4]^[5] Anggap $R = (x 1, x 2, ... , x φ (n)}$ sebagai sistem residu yang dikurangi ( $mod n$ ) dan biarkan $a$ koprima bilangan bulat $n$ . Buktinya bergantung dasar bahwa perkalian dengan $a$ yaitu $x i$ : dengan kata, jika $ax j \equiv ax k (mod n)$ maka $j = k$ . (Hukum pembatalxan ini dibuktikan dalam artikel Grup perkalian bilangan bulat modulo $n$ .^[6]) Yaitu, himpunan $R$ dan $aR = (ax 1, ax 2, ... , ax φ (n)}$ , dianggap sebagai himpunan kelas ( $mod n$ ), identik (sebagai himpunan), jadi produk dari semua bilangan di $R$ kongruen ( $mod n$ ) ke produk dari bilangan $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}},

dan menggunakan hukum pembatalan untuk

x i

dari teorema Euler:

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

Hasil bagi Euler

Hasil bagi Euler dari bilangan bulat a dengan n didefinisikan sebagai:

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

Kasus khusus dari hasil bagi Euler ketika n adalah bilangan prima disebut hasil bagi Fermat.

Bilangan ganjil n dengan $q_{n}(2)$ disebut bilangan Wieferich. Dengan 2^{Templat:Φ(n)} ≡ 1 (mod n²). Sebagai generalisasi, bilangan n koprima menjadi bilangan bulat positif a, dan n membagi $q_{n}(a)$ , disebut bilangan Wieferich (digeneralisasikan) ke basis a. Ini sama dengan mengatakan itu a^{Templat:Φ(n)} ≡ 1 (mod n²).

a	Bilangan n koprima a membagi $q_{n}(a)$ (mencari hingga 1048576)	Barisan 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, ... (all natural numbers)	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, ...

Basis terkecil b > 1 dari n adalah bilangan Wieferich

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

Lihat pula

Catatan

^
Lihat:
- Leonhard Euler (diterbitkan: 2 Agustus 1736; diterbitkan: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Bukti teorema tertentu tentang bilangan prima), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.
- Untuk detail lebih lanjut tentang makalah ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive.
^
Lihat:
- L. Euler (published: 1763) "Theoremata arithmetica nova methodo demonstrata" (Bukti metode baru dalam teori aritmetika), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Makalah ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam makalah ini, fungsi total Euler, $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad N primarum" (jumlah bagian prima ke N; yaitu, jumlah bilangan asli yang lebih kecil dari N dan relatif prima sampai N)
- Untuk detail lebih lanjut tentang makalah ini, lihat: The Euler Archive.
- Untuk review pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"
^ Ireland & Rosen, corr. 1 to prop 3.3.2
^ Hardy & Wright, thm. 72
^ Landau, thm. 75
^ Lihat lemma Bézout

Referensi

Disquisitiones Arithmeticae telah diterjemahkan dari bahasa Latin Ciceronian Gauss ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua makalahnya tentang teori bilangan: semua bukti timbal balik kuadrat, penentuan tanda jumlah Gauss, penyelidikan timbal balik biquadratic, dan catatan yang tidak diterbitkan.

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

Pranala luar

[1] Lihat:
Leonhard Euler (diterbitkan: 2 Agustus 1736; diterbitkan: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Bukti teorema tertentu tentang bilangan prima), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.

Untuk detail lebih lanjut tentang makalah ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive.

[2] Leonhard Euler (diterbitkan: 2 Agustus 1736; diterbitkan: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Bukti teorema tertentu tentang bilangan prima), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146.

[3] Untuk detail lebih lanjut tentang makalah ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive.

[2] Lihat:
L. Euler (published: 1763) "Theoremata arithmetica nova methodo demonstrata" (Bukti metode baru dalam teori aritmetika), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Makalah ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam makalah ini, fungsi total Euler, $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad N primarum" (jumlah bagian prima ke N; yaitu, jumlah bilangan asli yang lebih kecil dari N dan relatif prima sampai N)

Untuk detail lebih lanjut tentang makalah ini, lihat: The Euler Archive.

Untuk review pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"

[5] L. Euler (published: 1763) "Theoremata arithmetica nova methodo demonstrata" (Bukti metode baru dalam teori aritmetika), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Makalah ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam makalah ini, fungsi total Euler, $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad N primarum" (jumlah bagian prima ke N; yaitu, jumlah bilangan asli yang lebih kecil dari N dan relatif prima sampai N)

[6] Untuk detail lebih lanjut tentang makalah ini, lihat: The Euler Archive.

[7] Untuk review pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"

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

[4] Hardy & Wright, thm. 72

[5] Landau, thm. 75

[6] Lihat lemma Bézout

[1]

[2]

[3]

[4]

[5]

[6]