Wikipedia

Teorema Euler: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
123569yuuift (bicara | kontrib)
2.955 suntingan
Tidak ada ringkasan suntingan
Tag: Suntingan perangkat seluler Suntingan peramban seluler Suntingan seluler lanjutan
RaFaDa20631 (bicara | kontrib)
Pengurus
93.780 suntingan
 
(6 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 [[koprima]]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>▼
dimana: <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> olehkarena [[Pierre de Fermat|Fermat]] tidak menyertakan bukti teorema tersebut. Selanjutnya, Euler menerbitkan bukti lain dari teorema tersebut, yang berpuncak denganpada "Teorema Euler" dalam makalahpenelitiannya tahun 1763, di mana ia mencoba untuk menemukan eksponen terkecil yangsehinga 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 kongruensikekongruenan di atas benar, maka <math>a</math> dan <math>n</math> adalahsaling koprima.
 
TeoremaUntuk tersebutkasus <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 selanjutnyadengan digeneralisasikanmengalikan kedua ruas persamaan dengan [[Fungsi<math>a</math>, Carmichael|teorema Carmichael]].Euler dapat ditulis sebagai
 
▲: <math>a^{\varphi (n)}p \equiv 1p \pmod{np}</math>
Teorema dapat digunakan untuk mengurangi pangkat besar modulo <math>n</math>. Misalnya, pertimbangkan untuk mencari digit desimal tempat satuan dari <math>7^{222}</math>, yaitu <math>7^{222} \pmod{10}</math>. Bilangan bulat 7 dan 10 adalah coprima, dan <math>\varphi(10) = 4</math>. Jadi, teorema Euler <math>7^4 \equiv 1 \pmod{10}</math>, dan hasil diporoleh 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>.▼
 
Teorema Euler juga dapat diperumum lebih lanjut dengan [[Fungsi Carmichael|teorema Carmichael]].
Secara umum, mengurangi pangkat <math>a</math> modulo <math>n</math> (di mana <math>a</math> dan <math> n </math> adalah koprima), modulo <math>\varphi(n)</math> dalam eksponen <math>a</math>:▼
:jika <math>x \equiv y \pmod{\varphi(n)}</math>, maka <math>a^x \equiv a^y \pmod{n}</math>.▼
 
▲Teorema Euler dapat digunakan untuk mengurangi nilai pangkat yang besar pada modulo <math>n</math>. Misalnya, pertimbangkananggap kita perlu untuk mencari digit desimal tempat satuan dari <math>7^{222}</math>, yaitudengan kata lain, mencari nilai dari <math>7^{222} \pmod{10}</math>. BilanganKita bulatdapat 7mencari danbahwa 10 adalah coprima, dannilai <math>\varphi(10) = 4</math>, dan mengetahui angka 7 dan 10 saling koprima. JadiSelanjutnya, dengan menggunakan teorema Euler didapatkan <math>7^4 \equiv 1 \pmod{10}</math>,. danSelanjutnya hasilkita diporolehtinggal adalahmenyederhanakan bentuk <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>. seperti berikut
Teorema Euler mendasari [[RSA (cryptosystem)|RSA cryptosystem]], yang banyak digunakan dalam komunikasi [[Internet]]. Dalam kriptosistem ini, teorema Euler digunakan {{mvar|n}} sebagai hasil kali dari dua [[bilangan prima]] besar, dan keamanan sistem didasarkan pada tingkat kesulitan [[faktorisasi bilangan bulat|pemfaktoran]] bilangan bulat.▼
 
: <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>.
== Contoh ==
 
Untuk <math>n=p</math> [[bilangan prima|prima]]
▲Secara umum, mengurangi nilai pangkat dari <math>a</math> pada modulo <math>n</math> (di manadengan <math>a</math> dan <math> n </math> adalahsaling koprima), kita cukup bekerja pada modulo <math>\varphi(n)</math> dalam eksponenperpangkatan <math>a</math>:
:<math>a^{p-1}=1\pmod{p},</math> ▼
 
karena <math>\varphi(p)=p-1</math>.
▲: jika <math>x \equiv y \pmod{\varphi(n)}</math>, maka <math>a^x \equiv a^y \pmod{n}</math>.
Itu [[Teorema kecil Fermat]].
 
▲Teorema Euler mendasarimenjadi dasar [[RSA (cryptosystem)|RSAalgoritma cryptosystemRSA]], yang banyak digunakan dalam sistem komunikasi di [[Internet]]. Dalam kriptosistemalgoritma ini, teorema Euler digunakan bersama sebuah bilangan {{mvar|n}} sebagaiyang merupakan hasil kali dari dua [[bilangan prima]] besar,. danTingkat keamanan sistemalgoritma tersebut didasarkan pada tingkat kesulitan untuk [[faktorisasi bilangan bulat|pemfaktoranmemfaktorkan]] bilangan bulat{{mvar|n}}.
 
== Bukti ==
Terdapat beberapa cara untuk membuktikan Teorema Euler, berikut dua diantaranya.
1. Teorema Euler dapat dibuktikan dengan menggunakan konsep dari [[grup (matematika)|teori grup]]:<ref>Ireland & Rosen, corr. 1 to prop 3.3.2</ref>
 
Kelas residu modulo {{mvar | n}} yang coprime untuk {{mvar | n}} membentuk kelompok dalam perkalian (lihat artikel [[grup perkalian bilangan bulat modulo N|Grup perkalian bilangan bulat modulo {{mvar|''n''}}]]). [[Urutan (teori grup)|urutan]] dari grup adalah {{math|''φ''(''n'')}}. [[Teorema Lagrange (teori grup)|Teorema Lagrange]] urutan subgrup dari sebuah [[grup hingga]] membagi urutan seluruh grup, dalam hal ini {{math|''φ''(''n'')}}. Jika {{mvar|a}} bilangan [[koprima]] sampai {{mvar|n}} maka {{mvar|a}} salah satu kelas residu, dan pangkat {{math|''a'', ''a''{{sup|2}}, ... , ''a''{{sup|''k''}}}} modulo {{mvar|n}} subgrup dari grup kelas residu, dengan {{math|''a''{{sup|''k''}} &equiv; 1 (mod ''n'')}}. Teorema Lagrange mengatakan {{mvar|k}} harus membagi {{math|''φ''(''n'')}}, yaitu bilangan bulat {{mvar|M}} sedemikian rupa sehingga {{math|''kM'' {{=}} ''φ''(''n'')}}. Ini kemudian menyiratkan,▼
=== Teori grup ===
▲Teorema Euler dapat dibuktikan dengan menggunakan konsep dari [[grup (matematika)|teori grup]]:<ref>Ireland & Rosen, corr. 1 to prop 3.3.2</ref> Kelas residu modulo {{mvar | n}} yang coprime untuk {{mvar | n}} membentuk kelompok dalam perkalian (lihat artikel [[grup perkalian bilangan bulat modulo N|Grup perkalian bilangan bulat modulo {{mvar|''n''}}]]). [[Urutan (teori grup)|urutan]] dari grup adalah {{math|''φ''(''n'')}}. [[Teorema Lagrange (teori grup)|Teorema Lagrange]] urutan subgrup dari sebuah [[grup hingga]] membagi urutan seluruh grup, dalam hal ini {{math|''φ''(''n'')}}. Jika {{mvar|a}} bilangan [[koprima]] sampai {{mvar|n}} maka {{mvar|a}} salah satu kelas residu, dan pangkat {{math|''a'', ''a''{{sup|2}}, ... , ''a''{{sup|''k''}}}} modulo {{mvar|n}} subgrup dari grup kelas residu, dengan {{math|''a''{{sup|''k''}} &equiv; 1 (mod ''n'')}}. Teorema Lagrange mengatakan {{mvar|k}} harus membagi {{math|''φ''(''n'')}}, yaitu bilangan bulat {{mvar|M}} sedemikian rupa sehingga {{math|''kM'' {{=}} ''φ''(''n'')}}. Ini kemudian menyiratkan,
:<math>a^{\varphi(n)} = a^{kM} = (a^{k})^M \equiv 1^M =1 \equiv 1 \pmod{n}.</math>
 
=== Bukti langsung ===
2.Teorema Euler juga dapat dibuktikan secara Buktilangsung:<ref>Hardy & Wright, thm. 72</ref><ref>Landau, thm. 75</ref> MakaAnggap {{math|''R'' {{=}} {{(}}''x''{{sub|1}}, ''x''{{sub|2}}, ... , ''x''{{sub|''φ''(''n'')}}{{)}}}} jadilahsebagai [[sistem residu yang dikurangi]] ({{math|mod ''n''}}) dan biarkan {{mvar|a}} koprima bilangan bulat {{mvar|n}}. Buktinya bergantung dasar bahwa perkalian dengan {{mvar|a}} yaitu {{mvar|x{{sub|i}}}}: dengan kata, jika {{math|''ax{{sub|j}}'' &equiv; ''ax{{sub|k}}'' (mod ''n'')}} maka {{math|''j'' {{=}} ''k''}}. (Hukum pembatalanpembatalxan ini dibuktikan dalam artikel [[Grup perkalian bilangan bulat modulo N#Aksioma grup|Grup perkalian bilangan bulat modulo {{mvar|''n''}}]].<ref>Lihat [[lemma Bézout]]</ref>) Yaitu, himpunan {{mvar|R}} dan {{math|''aR'' {{=}} {{(}}''ax''{{sub|1}}, ''ax''{{sub|2}}, ... , ''ax''{{sub|''φ''(''n'')}}{{)}}}}, dianggap sebagai himpunan kelas ({{math|mod ''n''}}), identik (sebagai himpunan), jadi produk dari semua bilangan di {{mvar|R}} kongruen ({{math|mod ''n''}}) ke produk dari bilangan {{mvar|aR}}:
:<math>
\prod_{i=1}^{\varphi(n)} x_i \equiv
Baris 44 ⟶ 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^{p-1}=1\pmod{p},</math>
|Bilangan Wieferich pada basis <math>a</math>
|Barisan [[OEIS]]
|-
Baris 178 ⟶ 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 191 ⟶ 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 235 ⟶ 244:
| location = New York
| date = 1966}}
{{refend}}
 
{{div col end}}
== Pranala luar ==
* {{mathworld|EulersTotientTheorem|Euler's Totient Theorem}}
Baris 241 ⟶ 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"