Wikipedia

Teorema Euler: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
k perbaikan gaya bahasa
RaFaDa20631 (bicara | kontrib)
Pengurus
93.780 suntingan
 
(5 revisi perantara oleh 5 pengguna tidak ditampilkan)
Baris 1:
{{short description|Generalisasi teorema kecil Fermat ke modulus non-prima}}
{{about|Teorema Euler dalam teori bilangan||Daftar topik yang dinamai menurut Leonhard Euler}}
Dalam [[teori bilangan]], '''Teoremateorema Euler''' (juga dikenal sebagai '''Teoremateorema Fermat-EulerFermat–Euler''' atau '''Teoremateorema Totaltotal Euler''') menyatakan bahwa jika ''n'' dan ''a'' adalah [[Bilangan asli|bilangan bulat positif]] yang saling [[koprima]], maka ''a'' pangkat fungsi phi Euler dari ''n'' akan kongruen dengan satu, dalam [[aritmetika modular|modulo]] ''n'',. atau:Secara matematis hal ini dapat dinyatakan sebagai
 
: <math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>
 
dengan <math>\varphi(n)</math> adalah [[fungsi phi Euler]]. Pada tahun 1736, [[Leonhard Euler]] mempublikasikan bukti [[teorema kecil Fermat]] versinya,<ref>Lihat:
* Leonhard Euler (diterbitkan: 2 Agustus 1736; diterbitkan: 1741) [https://books.google.com/books?id=-ssVAAAAYAAJ&pg=RA1-PA141#v=onepage&q&f=false "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: [https://scholarlycommons.pacific.edu/euler-works/54/ The Euler Archive].</ref> karena [[Pierre de Fermat|Fermat]] tidak menyertakan bukti teorema tersebut. Selanjutnya, Euler menerbitkan bukti lain dari teorema tersebut, yang berpuncak pada "Teorema Euler" dalam makalahnyapenelitiannya tahun 1763, di mana ia mencoba untuk menemukan eksponen terkecil sehinga teorema kecil Fermat selalu bernilai benar.<ref>Lihat:
*L. Euler (published: 1763) [https://books.google.com/books?id=5uEAAAAAYAAJ&pg=PA74#v=onepage&q&f=false "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, <math>\varphi(n)</math>, 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: [http://www.math.dartmouth.edu/~euler/pages/E271.html The Euler Archive].
*Untuk review pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: [http://people.wcsu.edu/sandifere/History/Preprints/Talks/Rowan%202005%20Euler's%20three%20proofs.pdf Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"] {{Webarchive|url=https://web.archive.org/web/20060828195053/http://people.wcsu.edu/sandifere/History/Preprints/Talks/Rowan%202005%20Euler%27s%20three%20proofs.pdf |date=2006-08-28 }}</ref>
 
Kebalikan dari teorema Euler: jika kekongruenan di atas benar, maka <math>a</math> dan <math>n</math> saling koprima.
 
TeoremaUntuk kasus <math>n</math> adalah suatu bilangan prima <math>p</math>, teorema Euler adalah generalisasiperumuman dari [[teorema kecil Fermat]]. Pada kasus ini, nilai <math>\varphi(p)=p-1</math>, dan dapatdengan digeneralisasikanmengalikan lebihkedua lanjutruas persamaan dengan [[Fungsi<math>a</math>, Carmichael|teorema Carmichael]].Euler dapat ditulis sebagai
 
: <math>a^{p-1}=1 \equiv p \pmod{p},</math> ▼
 
Teorema Euler juga dapat diperumum lebih lanjut dengan [[Fungsi Carmichael|teorema Carmichael]].
 
Teorema Euler dapat digunakan untuk mengurangi nilai pangkat yang besar pada modulo <math>n</math>. Misalnya, anggap kita perlu untuk mencari digit desimal tempat satuan dari <math>7^{222}</math>, dengan kata lain, mencari nilai dari <math>7^{222} \pmod{10}</math>. Kita dapat mencari bahwa nilai <math>\varphi(10) = 4</math>, dan mengetahui angka 7 dan 10 saling koprima. Selanjutnya, dengan menggunakan teorema Euler didapatkan <math>7^4 \equiv 1 \pmod{10}</math>. Selanjutnya kita tinggal menyederhanakan bentuk <math>7^{222} \pmod{10}</math> seperti berikut
 
Teorema Euler dapat digunakan untuk mengurangi nilai pangkat yang besar pada modulo <math>n</math>. Misalnya, anggap kita perlu untuk mencari digit desimal tempat satuan dari <math>7^{222}</math>, dengan kata lain, <math>7^{222} \pmod{10}</math>. Bilangan bulat 7 dan 10 saling koprima, dan nilai <math>\varphi(10) = 4</math>. Selanjutnya, dengan menggunakan teorema Euler didapatkan <math>7^4 \equiv 1 \pmod{10}</math>, dan hasil diperoleh adalah: <math>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}</math>.
 
Secara umum, mengurangi nilai pangkat dari <math>a</math> pada modulo <math>n</math> (di manadengan <math>a</math> dan <math> n </math> saling koprima), kita cukup bekerja pada modulo <math>\varphi(n)</math> dalam perpangkatan <math>a</math>:
:jika <math>x \equiv y \pmod{\varphi(n)}</math>, maka <math>a^x \equiv a^y \pmod{n}</math>.▼
 
▲: jika <math>x \equiv y \pmod{\varphi(n)}</math>, maka <math>a^x \equiv a^y \pmod{n}</math>.
Teorema Euler menjadi dasar [[RSA|algoritma RSA]], yang banyak digunakan dalam sistem komunikasi di [[Internet]]. Dalam algoritma ini, teorema Euler digunakan bersama sebuah bilangan {{mvar|n}}, yang merupakan hasil kali dari dua [[bilangan prima]] besar, dan tingkat keamanan algoritma didasarkan pada tingkat kesulitan untuk [[faktorisasi bilangan bulat|memfaktorkan]] bilangan {{mvar|n}} tersebut.▼
 
▲Teorema Euler menjadi dasar [[RSA|algoritma RSA]], yang banyak digunakan dalam sistem komunikasi di [[Internet]]. Dalam algoritma ini, teorema Euler digunakan bersama sebuah bilangan {{mvar|n}}, yang merupakan hasil kali dari dua [[bilangan prima]] besar,. dan tingkatTingkat keamanan algoritma tersebut didasarkan pada tingkat kesulitan untuk [[faktorisasi bilangan bulat|memfaktorkan]] bilangan {{mvar|n}} tersebut.
== Contoh ==
Untuk <math>n=p</math> [[bilangan prima|prima]]
▲:<math>a^{p-1}=1\pmod{p},</math>
karena <math>\varphi(p)=p-1</math>.
Itu [[Teorema kecil Fermat]].
 
== Bukti ==
Baris 47 ⟶ 50:
 
== Hasil bagi Euler ==
'''Hasil bagi Euler''' dari bilangan bulat ''a'' dengan ''n'' didefinisikan sebagai:
 
:<math>q_n(a)=\frac{a^{\varphi(n)}-1}{n}</math>
 
Kasus[[Hasil bagi Fermat]] adalah kasus khusus dari hasil bagi Euler ketika ''n'' adalahberupa bilangan prima disebut [[hasil bagi Fermat]].
 
Bilangan ganjil ''n'' denganyang membagi <math>q_n(2)</math> disebut [[bilangan Wieferich]]. DenganHal tersebut setara dengan mengatakan 2<supmath>2^{{φ}}\varphi(''n'')</sup>} ≡\equiv 1 \ \ (\text{mod}\, ''n''<sup>^2)</supmath>). Sebagai generalisasiperumuman, sebuah bilangan ''n'' yang koprima menjadidengan bilangan bulat positif ''a'', dan ''n'' membagi <math>q_n(a)</math>, disebut bilangan Wieferich (digeneralisasikanyang diperumum) kepada basis ''a''. IniDengan samakata denganlain, mengatakanbilangan itutersebut memenuhi a<supmath>a^{{φ}}\varphi(''n'')</sup>} ≡\equiv 1 \ \ (\text{mod}\, ''n''<sup>^2)</supmath>).
 
Berikut adalah daftar bilangan Wieferich pada basis <math>a</math>, untuk <math>a=1\dots30</math>, yang dicari sampai 1048576.
{|class="wikitable"
 
|''a''
{| class="wikitable mw-collapsible mw-collapsed"
|Bilangan ''n'' koprima ''a'' membagi <math>q_n(a)</math> (mencari hingga 1048576)
|<math>a</math>
|Bilangan Wieferich pada basis <math>a</math>
|Barisan [[OEIS]]
|-
Baris 181 ⟶ 186:
|}
 
Basis terkecil ''b''dari <math>a > 1</math> darisehingga ''<math>n''</math> adalahmerupakan 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, ... {{OEIS|id=A250206}}
 
Baris 194 ⟶ 199:
 
== 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 timbaltentang balik''reciprocity'' kuadrat, penentuan tanda dari jumlah Gauss, penyelidikan timbal baliktentang ''biquadratic reciprocity'', dan catatan yang tidak diterbitkan.
{{divcol|colwidth=30em}}
 
{{refbegin}}
*{{citation
| last1 = Gauss | first1 = Carl Friedrich
Baris 238 ⟶ 244:
| location = New York
| date = 1966}}
{{refend}}
 
{{div col end}}
== Pranala luar ==
* {{mathworld|EulersTotientTheorem|Euler's Totient Theorem}}
Baris 244 ⟶ 251:
 
{{Portal bar|Matematika}}
{{Leonhard Euler}}
 
[[Kategori:Aritmetika modular]]
[[Kategori:Teorema dalam teori bilangan]]
[[Kategori:Artikel yang berisimemuat buktipembuktian]]
[[Kategori:Leonhard Euler]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Teorema_Euler"