Aritmetika modular: Perbedaan antara revisi

{{short description|ModuloPerhitungan komputasisisa pembagian dengan sebuah bilangan bulat tetap}}

[[Berkas:Clock group.svg|thumb|250px|right|Pengatur waktu pada jam ini menggunakan aritmatikaaritmetika 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.

[[Berkas:Diophantus-cover.jpg|jmpl|Laman judul edisi 1621 ''Aritmatika'' karya Diofantos, diterjemahkan ke dalam [[bahasa Latin]] oleh [[Claude Gaspard Bachet de Méziriac]].|kiri]]

[[India]] juga memiliki tradisi kuat dalam aritmetika. [[Aryabhata]] (476 - 550) secara sistematik mencari solusi bilangan bulat dari persamaan linear dengan dua variabel dan koefisien bilangan bulat. Algoritmanya dirujuk sebagai "Kuttaka" pada bukunya ''Âryabhatîya.''<ref>Agathe Keller. [http://halshs.ccsd.cnrs.fr/docs/00/04/96/19/PDF/Analyse.pdf Un commentaire indien du VIIème siècle, Bhâskara et le ganitapada de l’aryabhatiya. Histoire, Philosophie et Sociologie des sciences]. [[Universitas de Paris (2019)|Université Paris 7 - Denis Diderot]], 2000. Français. ffhalshs-00006349f</ref> Persamaan Diofantin derajat dua dipelajari [[Brahmagupta]] (598 - 668).<ref>{{Cite book|last=Sarasvati|first=S. S. Prakash|date=1986|url=|title=A critical study of Brahmagupta and his works|location=Delhi|publisher=|isbn=|pages=|url-status=live}}</ref> Pada abad ke-12, [[Bhāskara II]] menyempurnakan [[metode Chakravala]].

Masa [[Ilmu pengetahuan Islam abad pertengahan|Islam abad pertengahan]] memegang peran ganda dalam perkembangan aritmetika: menggabungkan pengetahuan yang didapatkan di Yunani, India, Cina, dan Eropa,<ref>{{Cite book|last=Pinès|first=Shlomo|date=1986|url=|title=Studies in Arabic versions of Greek texts and in Medieval science.|location=Leiden|publisher=|isbn=|pages=|url-status=live}}</ref> dan menciptakan penemuan baru. Hal ini termasuk studi mengenai sifat dari himpunan bilangan, seperti [[Bilangan prima|prima]], [[Bilangan sempurna|sempurna]], ramah (''amicable''), dan [[Bilangan poligonal|poligonal]].<ref name=":1">{{Cite book|date=2005|url=https://www.worldcat.org/oclc/317446627|title=L'âge d'or des sciences arabes : exposition présentée à l'Institut de monde arabe, Paris, 25 octobre 2005-19 mars 2006|location=[Arles]|publisher=Actes Sud|isbn=2-7427-5672-8|others=Alaoui, Brahim., Institut du monde arabe (France)|oclc=317446627}}</ref> Dalam konteks ini, Qusta bin Lûqâ melakukan terjemahan parsial buku ''[[Arithmetica]]'' milik [[Diofantos|Diofantos dari Alexandria]], di akhir abad ke-9.<ref name=":1" /> Pada masa yang sama, Al-Hajjaj menerjemahkan ''Elemen'' milik Euclid.<ref>{{Cite book|last=Berggren|first=John Lennart|date=1986|url=https://archive.org/details/episodesinmathem0000berg|title=Episodes in the Mathematics of Medieval Islam|location=|publisher=Springer|isbn=|pages=[https://archive.org/details/episodesinmathem0000berg/page/70 70]-71|url-status=live}}</ref> Koleganya, [[Al-Khwarizmi|Al-Kharizmi]] (sekitar 783 - 850), menulis buku mengenai numerisasi. Terjemahan bahasa Latin dari buku ini adalah ''Algoritmi de numero Indorum''.<ref>{{Cite journal|last=Crossley|first=John|last2=Henry|first2=Alan|date=1990|title=Thus Spake al-Khwārizimī: A Translation of the Text of Cambridge University Library Ms. li.vi.5|url=|journal=Historia Mathematica|volume=17|issue=|pages=103-131|doi=}}</ref> [[Tsabit bin Qurrah]] (836-901) mempelajari bilangan ''amicable'' dan bilangan sempurna.<ref>{{Cite book|last=Carmody|first=Francis J.|date=1941|url=|title=Thabit b. Qurra, Four Astronomical Tracts in Latin|location=Berkeley|publisher=|isbn=|pages=|url-status=live}}</ref> [[Ibnu Haitham]] (965 - 1039) melanjutkan hasil kerjanya dan menemukan [[teorema Wilson]].<ref>{{Cite journal|last=Rashed|first=Roshdi|date=1980|title=Ibn al-haytham et le théorème de Wilson|url=|journal=Archive for History of Exact Sciences|volume=22|issue=4|pages=305-321|doi=}}</ref>

=== <!-- Perkembanga===Perkembangan metode yang digunakan=== --> ===

Dua penemuan Gauss tersebut berasal dari pendekatan yang sama, dengan peralatan yang lebih maju ketimbang pada masa Fermat maupun Euler. Hal ini memungkinkan untuk menulis pembuktian yang lebih sederhana, walau menjadi lebih abstrak. Pendekatannya adalah dasar bagi aritmetika modular.<!-- belum semuanya dialihbahasakan -->

Pada awal tahun 1930-an, kantor sandi Polandia meminta matematikawan [[Marian Rejewski]] untuk memecahkan kode [[mesin Enigma]], yang digunakan oleh Jerman. Kode lawas, seperti [[sandi Caesar]], didefinisikan ulang sebagai transformasi matematis pada himpunan modulus Gaussian atas bilangan bulat.<!-- tolong koreksi -->nama atasobjek bilanganmatematika bulat.tersebut --> Istilah "aritmatika modular" digunakan untuk menjelaskan teknik ini.<!-- belum semuanya dialihbahasakan -->

Penerapan aritmetika modular tertua ada pada [[Bilanganbilangan bulat]]. {{Setelah menetapkan sebuah bilangan bulat <math|''>n'' > 1}}</math>, yang disebut dengan'' 'modulus'', kekongruenan modulo '',n'' dilakukan dengan melakukan perhitungan terhadap sisa hasil pembagian bilangan-bilangan terhadap ''n''. duaDua bilangan bulat dikatakan '''kongruen''' modulo {{mvar | n}}, jika selisih kedua bilangan tersebut merupakan kelipatan{{mvar | n}} adalah [[pembagian]] dari perbedaannya (yaitu, jika ada bilangan bulat {{math | '' k ''}} sehingga {{math|1=''a'' − ''b'' = ''kn''}}).

ModuloKekongruenan kekongruenan {{mvar |modulo ''n}}'' adalah sebuah [[relasi kekongruenan]], artinya inikekongruenan adalah [[relasi ekuivalensi]] yang kompatibel dengan operasi [[penambahan]], [[pengurangan]], dan [[perkalian]]. Modulo kekongruenanKekongruenan modulo{{mvar | n}} dilambangkan:

Tanda kurung berartimengartikan bahwa {{math|(mod ''n'')}} berlaku untuk seluruh persamaan, tidak hanya dikedua ruas kanan (di sini {{mvar | b}})persamaan. Notasi ini jangan disamakanberbeda dengan notasi {{math|''b'' mod ''n''}} (tanpa tanda kurung), yang mengacu pada [[operasi modulomodulus]]. Maka,Notasi {{math|''b'' mod ''n''}} menunjukkanmerujuk pada sebuah bilangan bulat unik {{mvar | <math>a}}</math> sehinggadengan {{<math|>0 ≤\leq ''a'' < ''n''}}</math> dan memenuhi <math>a \equiv b \; (\text{mod}\; n)</math> (misalnyaDengan kata lain, sisa <math>b</math> jikaketika dibagi dengan <math>n</math><ref name=":0">{{Cite web|date=2020-03-25|title=Comprehensive List of Algebra Symbols|url=https://mathvault.ca/hub/higher-math/math-symbols/algebra-symbols/|access-date=2020-08-12|website=Math Vault|language=en-US}}</ref>).

seperti dalam aritmatikaaritmetika modular untuk sistem 24 jam.

=== KelasBilangan kekongruenanaljabar ===

Setiap kelas residu modulo {{math | '' n ''}} dapat diwakili oleh salah satu anggotanya, meskipun biasanya mewakili setiap kelas residu dengan bilangan bulat nonnegatif terkecil yang termasuk dalam kelas<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Modular Arithmetic|url=https://mathworld.wolfram.com/ModularArithmetic.html|access-date=2020-08-12|website=mathworld.wolfram.com|language=en|access-date=2020-08-12}}</ref> (karena ini adalah sisa yang tepat yang dihasilkan dari pembagian). Dua anggota kelas residu yang berbeda modulo {{math | '' n ''}} adalah modulo tidak selaras {{math | '' n ''}}. Selain itu, setiap bilangan bulat milik satu dan hanya satu kelas residu modulo {{math | '' n ''}}.<ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=90}}</ref>

==== Sistem residu berkurang ====

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

* {{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}}