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.

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

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.

Kriptografi bukan satu-satunya bidang yang menggunakan istilah "aritmetika modular". Bidang ilmu [[teori informasi]] muncul pada akhir [[Perang Dunia II]]. Dalam kepemimpinan [[Claude Shannon]], bidang tersebut menjadi cabang dari [[matematika terapan]].<ref>{{Cite journal|last=Shannon|first=Claude|date=1948|title=A Mathematical Theory of Communications|url=|journal=Bell System Techical Journal|volume=27|issue=|pages=379-428 dan 623-656|doi=}}</ref> Walau kerahasiaan adalah salah satu topik diskusi, reabilitas (keandalan) juga menjadi tema utama bidang tersebut. [[Richard Hamming]] membuat algoritma pertama pada tahun 1950.<ref>{{Cite journal|last=Hamming|first=Richard|date=1950|title=Error Detecting and Correcting Codes|url=|journal=Bell System Techical Journal|volume=29|issue=|pages=150-163|doi=}}</ref> Sekali lagi, modulus bilangan buat digunakan teknik kodingpengkodean sederhana seperti ''checksum''. Pada tahun 1960, [[Kode siklik|kodingpengkodean]] yang lebih kuat dikembangkan, didasarkan pada polinomal dengan koefisien atas ''finite field''.<ref>{{Cite journal|last=Bose|first=Raj Chandra|last2=Ray-Chaudhuri|first2=D. K.|date=1960|title=On a class of error-correcting. Binary group codes|url=|journal=Information Control|volume=3|issue=|pages=68-79|doi=}}</ref> Aritmetika yang digunakan untuk objek tersebut umumnya menggunakan kata "modular".

[[Ilmu komputer]] menjadi kajian akademik pada awal tahun 1960.<ref>{{Cite book|last=Denning|first=Peter J.|date=2000|url=https://web.archive.org/web/20060525195404/http://www.idi.ntnu.no/emner/dif8916/denning.pdf|title=Computer Science: The Discipline|location=|publisher=|isbn=|series=Encyclopedia of Computer Science|pages=|url-status=live|access-date=2021-02-09|archive-date=2006-05-25|archive-url=https://web.archive.org/web/20060525195404/http://www.idi.ntnu.no/emner/dif8916/denning.pdf|dead-url=unfit}}</ref> Batasan tak terhindarkan dari struktur [[prosesor]] mengharuskan bilangan direpresentasikan dalam bentuk bit yang terbatas; menjustifikasi penggunaan modulo. Istilah "aritmetika modular" sering muncul, kita bahkan dapat menemukan [[bilangan Gaussian]] atau polinomial, sebagai contoh, untuk kalkulasi bilangan bulat berukuran besar.

Teknik yang dikembangkan untuk kriptografi, [[teori kodingkode]], dan aritmetika komputer, didasarkan pada konsep yang sama, memberikan suatu kesatuan di matematika terkait teori informasi.

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

{{See also|Relasi kekongruenan|Operasi modulus}}Hubungan kekongruenan bilangan bulat dapat ditulis sebagai

*[[Perkalian skalar]]: <math>ak \equiv bk</math>

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 {{mvar | <math>a}}</math> modulo {{<math|''>n''}}</math>. SifatBerikut beberapa sifat invers perkalian modular ditentukan oleh aturan berikut:

* Jika {{<math|''a>ax x''\equiv ≡ ''b'' (mod ''n'')}}</math> dan {{<math | '' >a ''^{-1}} koprima dengan {{</math> | '' n ''}}ada, maka solusi untuk kekongruenan linear initersebut diberikanadalah oleh {{<math|''>x'' ≡\equiv ''a''<sup>–1^{-1}b</supmath>''b'' (mod ''n'')}}

* [[Teorema kecil Fermat]]: Jika {{math | '' p ''}} adalah bilangan prima danyang tidak membagi {{math | '' a ''}}, maka {{math|''a'' ^{''p'' – 1} ≡ 1 (mod ''p'')}}.

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