Aritmetika modular: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
perbaikan gaya bahasa |
k perbaikan gaya bahasa |
||
Baris 1:
{{short description|
[[Berkas:Clock group.svg|thumb|250px|right|Pengatur waktu pada jam ini menggunakan
Dalam [[matematika]] dan khususnya pada [[teori bilangan aljabar]], '''aritmetika modular''' adalah metode [[aritmetika]] untuk menyelesaikan permasalahan mengenai [[bilangan bulat]]. Ide dasar dari aritmetika modular adalah bekerja dengan sisa hasil pembagian bilangan, bukan dengan bilangan itu sendiri. Salah satu contoh dari aritmetika modular ada pada [[sistem 12-jam]], di mana hari dibagi menjadi dua periode 12-jam. Jika sekarang jarum jam menunjukan pukul 7:00, maka 8 jam kemudian akan menunjukan pukul 3:00. Penambahan sederhana akan menghasilkan {{nowrap|7 + 8 {{=}} 15}}. Namun karena jam "berulang" setiap 12 jam, angka 15 "sama dengan" angka 3; ini adalah contoh ''aritmetika modulo'' 12.
Baris 26:
Pada tahun 1621, Claude-Gaspard Bachet de Méziriac <!-- Mungkin ada alih bahasa yang lebih baik, dari nama orang ini? -->menerjemahkan buku Diofantos ke bahasa Latin, yang memicu ketertarikan matematikawan saat itu. [[Pierre de Fermat]] banyak memberikan pernyataan matematika, tiga yang terkenal adalah [[Teorema Terakhir Fermat|teorema terakhir]]-nya, teorema jumlah dua persegi, dan [[Teorema kecil Fermat|teorema kecil]]-nya. [[Marin Mersenne]] mencari [[Bilangan prima Mersenne|bilangan prima yang mememiliki sifat unik]]. Fermat berkorespodensi dengannya, menulis [terjemahan] "Jika saya mengetahui alasan fundamental mengapa 3, 5, 7, 17, 257, 65537, ..., adalah bilangan prima, sepertinya saya akan menemukan hal yang sangat indah dalam masalah ini, karena saya sudah menemukan hal hebat yang saya bagikan kepadamu saat ini".<ref>Fermat, ''Korespodensi'', sebuah surat kepada Marin Mersenne, 25 Desember 1640.</ref> Bilangan tersebut dikenal sebagai [[bilangan Fermat]], walau sifat keprimaannya bilangan-bilangan tersebut ternyata hanya tebakan yang keliru dari Fermat. [[René Descartes|Rene Descartes]] melakukan penelitian tanpa hasil, dalam membuktikan jika sisa pembagian [[bilangan prima]] dengan 8 bernilai 1 atau 3, bilangan prima tersebut dapat ditulis dalam bentuk <math>x^2+2y^2</math>.
=== Kontribusi Carl Friedrich Gauss ===
Baris 61:
=== Kekongruenan bilangan bulat ===
{{See also|operasi modulus}}
Penerapan aritmetika modular tertua ada pada [[
Dua bilangan bulat dikatakan '''kongruen''' modulo {{mvar | n}}, jika selisih kedua bilangan tersebut adalah kelipatan{{mvar | n}} (yaitu, jika ada bilangan bulat {{math | '' k ''}} sehingga {{math|1=''a'' − ''b'' = ''kn''}}).
Modulo kekongruenan {{mvar | n}} adalah [[relasi kekongruenan]], artinya ini adalah [[relasi ekuivalensi]] yang kompatibel dengan operasi [[penambahan]], [[pengurangan]], dan [[perkalian]]. Modulo kekongruenan {{mvar | n}} dilambangkan:
Baris 161 ⟶ 163:
=== Invers perkalian ===
Tidak semua relasi kekongruenan modulo <math>n</math> memiliki invers perkalian. Eksistensi bilangan bulat <math>a^{-1}</math> (sehingga <math>aa^{-1} \equiv 1</math>) ada jika dan hanya jika <math>a</math> saling koprima dengan modulus <math>n</math>. Secara khusus, jika <math>p</math> adalah bilangan prima maka <math>a</math> (yang terletak diantara <math>0 < a < p</math>) akan selalu koprima dengan <math>p</math>. Dalam kasus ini, invers perkalian kekongruenan modulo <math>p</math> ada untuk semua bilangan yang tidak kongruen dengan nol. Bilangan bulat <math>a^{-1}</math> disebut'' [[invers perkalian modular]] ''dari
* Jika <math>a \equiv b</math> dan <math>a^{-1}</math> ada, maka berlaku <math>a^{-1} \equiv b^{-1} \pmod{n}</math>. Pada kasus <math>a= b</math>, hal ini dapat digunakan untuk menunjukkan ketunggalan invers perkalian.
* Jika
Perkalian invers {{math|''x'' ≡ ''a''<sup>–1</sup> (mod ''n'')}} dapat dihitung secara efisien dengan menyelesaikan [[identitas Bézout|Persamaan Bézout]] <math> ax + ny = 1 </math> untuk <math> x, y </math>, menggunakan [[algoritme Euklides diperluas]].▼
▲
=== Sifat lain ===
Berikut daftar beberapa hasil lebih lanjut terkait hubungan kekongruenan:
* [[Teorema kecil Fermat]]: Jika {{math | '' p ''}} adalah bilangan prima
* [[Teorema Euler]]: Jika {{math | '' a ''}} dan {{math | '' n ''}} koprima, maka {{math|''a'' <sup>''φ''(''n'')</sup> ≡ 1 (mod ''n'')}}, dengan {{math | '' φ ''}} adalah [[fungsi total Euler]]
* Konsekuensi sederhana dari teorema kecil Fermat adalah jika {{math | '' p ''}} adalah bilangan prima, maka {{math|''a''<sup>−1</sup> ≡ ''a'' <sup>''p'' − 2</sup> (mod ''p'')}} adalah kebalikan perkalian dari {{math|0 < ''a'' < ''p''}}. Lebih umum lagi, dari teorema Euler, jika {{math | '' a ''}} dan {{math | '' n ''}} adalah koprima, maka {{math|''a''<sup>−1</sup> ≡ ''a'' <sup>''φ''(''n'') − 1</sup> (mod ''n'')}}.
| |||