Aritmetika modular: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.9 |
Fitur saranan suntingan: 3 pranala ditambahkan. |
||
| (3 revisi perantara oleh 3 pengguna tidak ditampilkan) | |||
Baris 2:
[[Berkas:Clock group.svg|thumb|250px|right|Pengatur waktu pada jam ini menggunakan aritmetika modulo 12.]]
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.
Walau sudah dipelajari sejak kuno, sejarawan umumnya mengasosiasikan kemunculan aritmetika modular dengan tahun 1801, tahun publikasi buku ''[[Disquisitiones Arithmeticae]] '' karya [[Carl Friedrich Gauss]]. Pendekatan yang ia gunakan mempermudah penjelasan [[Konjektur|konjektur-konjektur]] terkenal, dan menyederhanakan bukti-bukti penting. Implikasi karya Gauss juga ditemukan pada bidang selain [[teori bilangan]], seperti [[aljabar]] dan [[geometri]].
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>.
<!-- ===Perkembangan metode yang digunakan=== -->
=== Kontribusi Carl Friedrich Gauss ===
Baris 36:
Aritmetika modular awalnya diterapkan kepada bilangan bulat, lalu ke polinomial, dilanjutkan kepada himpunan bilangan baru yang sekarang disebut dengan [[bilangan Gaussian]].
Semua persamaan Diofantin Fermat sudah terselesaikan saat ini, kecuali untuk teorema terakhirnya. Beberapa konjektur baru muncul. Sebagai contoh, jika ''a'' dan ''b'' saling [[Koprima (bilangan)|koprima]], apakah barisan aritmetika dengan nilai awal ''a'' dan kelipatan ''b'' memiliki bilangan prima, jika iya berapa banyak? Gauss dan matematikawan lain seperti Legendre berhipotesis bahwa ada takhingga prima di barisan tersebut, namun mereka tidak mampu membuktikannnya.
Aritmetika modular juga semakin diperkaya. Dirichlet, seorang siswa Gauss membuktikan teorema ''aritmetic progression''<ref>{{Cite journal|last=Dirichlet|first=|date=1840|title=Recherches de diverses applications de l'analyse infinitésimale à la théorie des nombres|url=|journal=Journal de Crelle|volume=21|issue=|pages=|doi=}}</ref> dengan mengembangkan konsep [[Karakter Dirichlet|karakter]], sekaligus memberi dasar formal untuk ilmu [[teori bilangan analitik]]. <!-- belum semuanya dialihbahasakan -->
Baris 96:
=== Bilangan aljabar ===
{{Main|Bilangan Gaussian}}
Pada kasus polinomial dengan koefisien bilangan bulat, sifat pembagian hanya berlaku untuk polinomial dengan koefisien derajat tersebesar bernilai 1 atau -1. Bagian ini membahas modulus berupa polinomial <math>X^2+1</math>, dengan struktur modular yang didapatkan masih bagian dari [[Gelanggang (matematika)|gelanggangnya]]. Gelanggang ini berisi himpunan bilangan dalam bentuk <math>\alpha + i \beta</math>, dengan <math>\alpha</math> dan <math>\beta</math> berupa bilangan bulat dan <math>i</math> berupa [[Bilangan imajiner|unit bilangan imajiner]], yang berkorespodensi dengan monomial <math>X</math>. Himpunan tersebut dikenal sebagai bilangan
=== Sistem residu ===
Baris 150:
Untuk sebarang nilai <math>a, b, c</math>. Lebih lanjut, operasi penjumlahan dan perkalian tetap berlaku pada relasi kekongruen modulo <math>n</math>. Jika <math>a_1, b_1, a_2, b_2 </math> memenuhi <math>a_1 \equiv b_1</math> dan <math>a_2 \equiv b_2</math>, maka <math>a_1 + a_2 \equiv b_1 + b_2</math> dan <math>a_1a_2 \equiv b_1b_2</math>. Hal ini juga menyebabkan beberapa operasi lain tetap berlaku:
* Penjumlahan skalar: <math>a+k \equiv b+k</math> dan <math>a-k \equiv b-k</math>
*[[Perkalian skalar]]: <math>ak \equiv bk</math>
* Perpangkatan: <math>a^k \equiv b^k</math>, untuk bilangan bulat non-negatif <math>k</math>
* Untuk polinomial <math>p(x)</math> dengan koefisien-koefisien bilangan bulat, berlaku <math>p(a) \equiv p(b)</math>
Baris 161:
=== 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 <math>a</math> modulo <math>n</math>. Berikut beberapa sifat invers perkalian modular:
* 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.
Baris 184:
Dalam matematika teoretis, aritmatika modular adalah salah satu fondasi [[teori bilangan]], menyentuh hampir setiap aspek studinya, dan itu juga digunakan secara luas dalam [[teori grup]], [[teori gelanggang]], [[teori simpul]], dan [[aljabar abstrak]]. Dalam matematika terapan, ini digunakan dalam [[aljabar komputer]], [[kriptografi]], [[ilmu komputer]], [[kimia]] dan [[seni visual|visual]] dan seni [[musik]]al.
Aplikasi yang sangat praktis adalah menghitung checksum dalam pengenal bilangan deret. Misalnya, [[Nomor Buku Standar Internasional]] (ISBN) menggunakan aritmatika modulo 11 (untuk 10 digit ISBN) atau modulo 10 (untuk ISBN 13 digit) untuk deteksi kesalahan. Demikian juga, [[Nomor Rekening Bank Internasional]] (IBAN), misalnya, menggunakan aritmatika modulo 97 untuk melihat kesalahan input pengguna di nomor rekening bank. Dalam kimia, digit terakhir dari [[nomor registrasi CAS]] (nomor pengenal unik untuk setiap [[senyawa kimia]]) adalah [[digit pemeriksa]], yang dihitung dengan mengambil digit terakhir dari dua bagian pertama [[Nomor CAS]] dikalikan 1, digit sebelumnya dikalikan 2, digit sebelumnya dikali 3 dll., menjumlahkan semua ini dan menghitung.
Dalam kriptografi, aritmatika modular secara langsung mendukung sistem [[Kriptografi kunci publik|kunci publik]] seperti [[RSA (algoritme)|RSA]] dan [[Pertukaran kunci Diffie–Hellman|Diffie–Hellman]], dan menyediakan [[finite field]] yang mendasari [[kurva elips]], dan digunakan dalam berbagai [[algoritma kunci simetris]] termasuk [[Standar Enkripsi Lanjutan]] (AES), [[Algoritma Enkripsi Data Internasional]] (IDEA), dan [[RC4]]. RSA dan Diffie–Hellman menggunakan [[eksponen modular]].
Dalam aljabar komputer, aritmatika modular biasanya digunakan untuk membatasi ukuran koefisien integer dalam penghitungan dan data menengah. Digunakan dalam [[faktorisasi polinomial]], masalah di mana semua algoritma efisien yang diketahui menggunakan aritmatika modular. Digunakan oleh implementasi yang paling efisien dari algoritma [[pembagi persekutuan terbesar polinomial]], eksak [[aljabar linear]] dan [[basis Gröbner]] di atas bilangan bulat dan [[bilangan rasional]]. Seperti yang diposting di [[Fidonet]] pada tahun 1980-an dan diarsipkan di [[Rosetta Code]], aritmatika modular digunakan untuk menyangkal [[konjektur jumlah pangkat Euler]] pada [[Sinclair QL]] [[mikrokomputer]] menggunakan hanya seperempat dari presisi integer yang digunakan oleh [[CDC 6600]] [[superkomputer]] untuk membantahnya dua dekade sebelumnya melalui [[pencarian brute force]].<ref>{{Cite web|title=Euler's sum of powers conjecture|url=https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#QL_SuperBASIC|access-date=2020-11-11|website=rosettacode.org|language=en}}</ref>
Dalam ilmu komputer, aritmatika modular sering diterapkan dalam [[operasi bitwise]] dan operasi lain yang melibatkan lebar tetap, [[struktur data]] siklik. [[Operasi modulo]], seperti yang diterapkan di banyak [[bahasa pemrograman]] dan [[kalkulator]], adalah aplikasi aritmetika modular yang sering digunakan dalam konteks. Operator logika [[XOR]] menjumlahkan 2 bit, modulo 2.
Baris 297:
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Section 31.3: Modular arithmetic, pp. 862–868.
* [http://genealogy.math.ndsu.nodak.edu/id.php?id=3545 Anthony Gioia], ''Number Theory, an Introduction'' Reprint (2001) Dover. {{isbn|0-486-41449-3}}.
* {{cite book |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |url=https://archive.org/details/elementaryintrod0000long_m1z0_2ndedi |edition=2nd |publisher=[[D. C. Heath and Company]] |location=Lexington |lccn=77171950}}
* {{cite book |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |url=https://archive.org/details/elementsofnumber0000pett |url-access=registration |publisher=[[Prentice Hall]] |location=Englewood Cliffs |lccn=71081766}}
* {{cite book |last=Sengadir |first=T. |title=Discrete Mathematics and Combinatorics |year=2009 |publisher=Pearson Education India |location=Chennai, India |isbn=978-81-317-1405-8 |oclc=778356123}}
| |||