Teorema Euler

Templat:Short description Templat:About 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 Euler dari n akan kongruen dengan satu dalam modulo n. Secara matematis hal ini dapat dinyatakan sebagai

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

dengan $φ (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 penelitiannya 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.

Untuk kasus $n$ adalah suatu bilangan prima $p$ , teorema Euler adalah perumuman dari teorema kecil Fermat. Pada kasus ini, nilai $φ (p) = p - 1$ , dan dengan mengalikan kedua ruas persamaan dengan $a$ , teorema Euler dapat ditulis sebagai

a^{p} \equiv p (\mod p)

Teorema Euler juga dapat diperumum 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, mencari nilai dari $7^{222} (\mod 10)$ . Kita dapat mencari bahwa nilai $φ (10) = 4$ , dan mengetahui angka 7 dan 10 saling koprima. Selanjutnya, dengan menggunakan teorema Euler didapatkan $7^{4} \equiv 1 (\mod 10)$ . Selanjutnya kita tinggal menyederhanakan bentuk $7^{222} (\mod 10)$ seperti berikut

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)

.

Secara umum, mengurangi nilai pangkat dari $a$ pada modulo $n$ (dengan $a$ dan $n$ saling koprima), kita cukup bekerja pada modulo $φ (n)$ dalam perpangkatan $a$ :

jika

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

, maka

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

.

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

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 Templat:Mvar yang coprime untuk Templat:Mvar membentuk kelompok dalam perkalian (lihat artikel [[grup perkalian bilangan bulat modulo N|Grup perkalian bilangan bulat modulo Templat:Mvar]]). urutan dari grup adalah Templat:Math. Teorema Lagrange urutan subgrup dari sebuah grup hingga membagi urutan seluruh grup, dalam hal ini Templat:Math. Jika Templat:Mvar bilangan koprima sampai Templat:Mvar maka Templat:Mvar salah satu kelas residu, dan pangkat Templat:Math modulo Templat:Mvar subgrup dari grup kelas residu, dengan Templat:Math. Teorema Lagrange mengatakan Templat:Mvar harus membagi Templat:Math, yaitu bilangan bulat Templat:Mvar sedemikian rupa sehingga Templat:Math. Ini kemudian menyiratkan,

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

Bukti langsung

Teorema Euler juga dapat dibuktikan secara langsung:^[4]^[5] Anggap Templat:Math sebagai sistem residu yang dikurangi (Templat:Math) dan biarkan Templat:Mvar koprima bilangan bulat Templat:Mvar. Buktinya bergantung dasar bahwa perkalian dengan Templat:Mvar yaitu Templat:Mvar: dengan kata, jika Templat:Math maka Templat:Math. (Hukum pembatalxan ini dibuktikan dalam artikel [[Grup perkalian bilangan bulat modulo N#Aksioma grup|Grup perkalian bilangan bulat modulo Templat:Mvar]].^[6]) Yaitu, himpunan Templat:Mvar dan Templat:Math, dianggap sebagai himpunan kelas (Templat:Math), identik (sebagai himpunan), jadi produk dari semua bilangan di Templat:Mvar kongruen (Templat:Math) ke produk dari bilangan Templat: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),

dan menggunakan hukum pembatalan untuk Templat:Mvar dari teorema Euler:

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

Hasil bagi Euler

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

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

Hasil bagi Fermat adalah kasus khusus dari hasil bagi Euler ketika n berupa bilangan prima.

Bilangan ganjil n yang membagi $q_{n} (2)$ disebut bilangan Wieferich. Hal tersebut setara dengan mengatakan $2^{φ (n)} \equiv 1 (mod n^{2})$ . Sebagai perumuman, sebuah bilangan n yang koprima dengan bilangan bulat positif a, dan n membagi $q_{n} (a)$ , disebut bilangan Wieferich (yang diperumum) pada basis a. Dengan kata lain, bilangan tersebut memenuhi $a^{φ (n)} \equiv 1 (mod n^{2})$ .

Berikut adalah daftar bilangan Wieferich pada basis $a$ , untuk $a = 1 \dots 30$ , yang dicari sampai 1048576.

$a$	Bilangan Wieferich pada basis $a$	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)	Templat: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, ...	Templat: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, ...	Templat: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, ...	Templat:OEIS link
6	1, 66161, 330805, 534851, 2674255, 3152573, 10162169, 13371275, 50810845, 54715147, 129255493, 148170931, 254054225, 273575735, 301121113, 383006029, 646277465, ...	Templat: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, ...	Templat: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, ...	Templat: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, ...	Templat:OEIS link
12	1, 2693, 123653, 1812389, 2349407, 12686723, 201183431, 332997529, ...	Templat: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, ...	Templat: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, ...

Basis terkecil dari $a > 1$ sehingga $n$ merupakan bilangan Wieferich termuat dalam barisan

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, ... Templat:OEIS

Lihat pula

Catatan

Templat:Reflist

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 tentang reciprocity kuadrat, penentuan tanda dari jumlah Gauss, penyelidikan tentang biquadratic reciprocity, dan catatan yang tidak diterbitkan. Templat:Divcol Templat:Refbegin

Templat:Refend Templat:Div col end

Pranala luar

Templat:Portal bar Templat:Leonhard Euler

↑
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, $φ (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" Templat:Webarchive
↑ Ireland & Rosen, corr. 1 to prop 3.3.2
↑ Hardy & Wright, thm. 72
↑ Landau, thm. 75
↑ Lihat lemma Bézout

[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, $φ (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" Templat:Webarchive

[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, $φ (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" Templat:Webarchive

[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]

Teorema Euler

Daftar isi

Bukti

Teori grup

Bukti langsung

Hasil bagi Euler

Lihat pula

Catatan

Referensi

Pranala luar

Menu navigasi

Teorema Euler

Bukti

Teori grup

Bukti langsung

Hasil bagi Euler

Lihat pula

Catatan

Referensi

Pranala luar

Menu navigasi

Pencarian