Wikipedia

Aritmetika modular: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
Menambahkan →Sejarah: , hasil alih bahasa dari artikel Wikipedia Bahasa Perancis fr: Arithmétique modulaire; Lihat sejarahnya untuk atribusi.
Kth Mariachi (bicara | kontrib)
39 suntingan
Fitur saranan suntingan: 3 pranala ditambahkan.
 
(14 revisi perantara oleh 5 pengguna tidak ditampilkan)
Baris 1:
{{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.
Dalam [[matematika]], '''aritmetika modular''' adalah sistem [[aritmetika]] untuk [[bilangan bulat]], di mana angka "membungkus" saat mencapai nilai tertentu, yang disebut '''modulus'''. Pendekatan modern untuk aritmatika modular dikembangkan oleh [[Carl Friedrich Gauss]] dalam bukunya '' [[Disquisitiones Arithmeticae]] '', yang diterbitkan pada tahun 1801.
 
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]].
Penggunaan yang umum dari aritmatika modular adalah dalam [[sistem 12-jam]], di mana hari dibagi menjadi dua periode 12-jam. Jika sekarang jam 7:00, maka 8 jam kemudian menjadi 3:00. Penambahan sederhana akan menghasilkan {{nowrap|7 + 8 {{=}} 15}}, tapi jam "berputar" setiap 12 jam. Karena angka jam dimulai kembali setelah mencapai 12, ini adalah aritmetika '' modulo '' 12. Dalam definisi di bawah, 15 adalah '' kongruen '' dengan 3 modulo 12, jadi "15:00" pada [[24 jam]] ditampilkan "3:00" pada format 12 jam.
 
Kegunaan aritmetika modular meningkat pada abad ke-20. Operasi aritmetika dasar pada komputer yang bekerja pada jumlah bit yang tetap, pada dasarnya adalah operasi aritmetika modular. Penerapan pada bidang industri memicu perkembangan [[Algoritme|algoritma]] aritmetika modular.
 
== Sejarah ==
 
=== Asal mula ===
[[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]]
Pada abad ke-3 SM, [[Euklides]] merumuskan fondasi-fondasi [[aritmetika]] dalam bukunya ''[[Elemen Euklides|Element]]''. Di dalamnya, terdapat sebuah [[Lema (matematika)|lema]] yang umum dirujuk sebagai [[Lemma Euklidean|lema Euklides]], versi awal dari [[teorema dasar aritmetika]] dan studi mengenai [[bilangan sempurna]]<ref>{{Cite journal|last=Heath|first=Thomas|date=1911|title=The thirteen books of Euclid's Elements|url=|journal=The Mathematical Gazette|volume=6|issue=92|pages=98-101|doi=}}</ref> dalam proposisi 36 pada bukunya ke-9.<ref>{{Cite web|title=Euclid's Elements, Book IX, Proposition 36|url=https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX36.html|website=mathcs.clarku.edu|access-date=2021-02-09}}</ref> [[Diofantos|Diofantos dari Alexandria]] (sekitar 250 M) menulis buku ''[[Arithmetica]]'' yang memuat 130 persamaan. Sebagian besar isinya membahas permasalahan yang memiliki hanya satu solusi, baik dalam bentuk pecahan maupun bilangan bulat. Buku tersebut juga menunjukkan bahwa jumlah dari dua [[bilangan sempurna]] tidak pernah dalam bentuk <math>4n+3</math>. Bentuk persamaan yang ia bahas, dengan koefisien persamaan dan solusi yang diharapkan berupa bilangan bulat, saat ini dikenal sebagai [[persamaan Diofantin]].<!-- tambahkan perkembangan di China, India, dan Islam -->
Pada abad ke-3 SM, [[Euklides]] merumuskan fondasi-fondasi [[aritmetika]] dalam bukunya ''[[Elemen Euklides|Element]]''. Di dalamnya, terdapat sebuah [[Lema (matematika)|lema]] yang umum dirujuk sebagai [[Lemma Euklidean|lema Euklides]], versi awal dari [[teorema dasar aritmetika]] dan studi mengenai [[bilangan sempurna]]<ref>{{Cite journal|last=Heath|first=Thomas|date=1911|title=The thirteen books of Euclid's Elements|url=|journal=The Mathematical Gazette|volume=6|issue=92|pages=98-101|doi=}}</ref> dalam proposisi 36 pada bukunya ke-9.<ref>{{Cite web|title=Euclid's Elements, Book IX, Proposition 36|url=https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX36.html|website=mathcs.clarku.edu|access-date=2021-02-09}}</ref> [[Diofantos|Diofantos dari Alexandria]] (sekitar 250 M) menulis buku ''[[Arithmetica]]'' yang memuat 130 persamaan. Sebagian besar isinya membahas permasalahan yang memiliki hanya satu solusi, baik dalam bentuk pecahan maupun bilangan bulat. Buku tersebut juga menunjukkan bahwa jumlah dari dua [[bilangan sempurna]] tidak pernah dalam bentuk <math>4n+3</math>. Bentuk persamaan yang ia bahas, dengan koefisien persamaan dan solusi yang diharapkan berupa bilangan bulat, saat ini dikenal sebagai [[persamaan Diofantin]].
 
Aritmetika modular juga berkembang di [[Cina]]. Sekitar 300 M, [[Sunzi Suanjing]] menulis risalah matematika, yang pada permasalahan ke-26 di bab ke-3 berisi: "Anggap ada barang yang jumlahnya tidak kita ketahui. Dengan menghitung tiga demi tiga, ada tersisa dua barang. Dengan menghitung lima demi lima, ada sisa tiga barang, dan ketika dihitung tujuh demi tujuh, ada sisa dua. Berapa banyak barang yang ada disana?".<ref>{{Cite book|last=Martzloff, Jean-Claude.|first=|date=1988|url=https://www.worldcat.org/oclc/416811520|title=Histoire des mathématiques chinoises|location=Paris|publisher=Masson|isbn=2-225-81265-9|pages=129|others=Impr. Louis-Jean)|oclc=416811520|url-status=live}}</ref>
 
[[Qin Jiushao]] (1202-1261) mengembangkan [[teorema sisa Cina]] dalam [[Risalah Matematika dalam Sembilan Bab|risalah matematika yang ia tulis]]. Materi pada risalah tesebut sangat dalam; membahas sistem kekongruenan linear pada kasus [[Operasi modulus|modulus-modulus]] pada sistem tidak saling koprima. [[George Sarton]] menyatakan bahwa karyanya pada sistem kekongruenan melebihi [[Leonhard Euler]] dan [[Carl Friedrich Gauss|Gauss]].<ref>{{Cite book|last=Chen|first=Joseph C. Y.|date=1996-03-01|url=https://books.google.co.id/books?id=2Wxj0SW9hBgC&pg=PA224&redir_esc=y#v=onepage&q&f=false|title=Early Chinese Work in Natural Science: A Re-examination of the Physics of Motion, Acoustics, Astronomy and Scientific Thoughts|location=|publisher=Hong Kong University Press|isbn=978-962-209-385-0|pages=224|language=en|url-status=live}}</ref> Namun, karya Qin Jiushao tidak tedengar di luuar Cina sebelum abad ke-20. Karyanya ditemukan ulang oleh sejarawan [[Joseph Needham]]. Di sisi lain, kemiripan notasi yang digunakan di Arab dan Cina mengusulkan ada kontak yang terjadi pada periode-periode sebelumnya.<ref>{{Cite journal|last=Chemla|first=Karine|date=1994|title=Similarities between chineese and arabic mathematical writings : (I) root extraction|url=|journal=Arabic Sciences and Philosophy|volume=4|issue=2|pages=207-266|doi=}}</ref>
 
[[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>
 
=== Perkembangan di Eropa ===
[[Berkas:Pierre de Fermat.jpg|jmpl|[[Pierre de Fermat]] banyak berkontribusi mengembangkan aritmatika. Sifat-sifat [[pembagian Euklides]], dasar dari aritmatika modular, banyak digunakan oleh matematikawan saat ini.]]
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>.<!-- Metode yang digunakan
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
Abad ke-20
Kriptografi
Teori informasi -->
 
<!-- ===Perkembangan metode yang digunakan=== -->
== Kongruensi ==
{{About|notasi ''(mod {{mvar|n}})''|operasi biner ''mod({{mvar|a,n}})'' |operasi modulo|section=yes}}
 
=== Kontribusi Carl Friedrich Gauss ===
[[Bilangan bulat]] {{math|''n'' > 1}}, disebut '' 'modulus' '', dua bilangan bulat dikatakan '''kongruen''' modulo {{mvar | n}}, jika {{mvar | n}} adalah [[pembagian]] dari perbedaannya (yaitu, jika ada bilangan bulat {{math | '' k ''}} sehingga {{math|1=''a'' − ''b'' = ''kn''}}).
[[Berkas:Carl Friedrich Gauss.jpg|kiri|jmpl|[[Carl Friedrich Gauss]] adalah penemu cabang matematika yang sekarang disebut ''aritmetika modular''.]]
Ketika berusia 17 tahun, [[Carl Friedrich Gauss|Gauss]] membuktikan teorema ''quadratic reciprocity''. Setahun kemudian, pada 30 Maret 1796, ia menyadari kalkulasi aritmetika-nya memungkinkan untuk mengontruksi [[heptadekagon]] (poligon dengan 17 sisi) dengan menggunakan jangka dan penggaris, sebuah permasalahan yang tidak terjawab sejak masa kuno. Akhirnya pada 1801, ia mempublikasikan ''[[Disquisitiones Arithmeticae]] ''(''Penelitian tentang Aritmetika''), dan dijuluki ''pangeran matematikawan''.<ref>{{Cite book|last=Naudin, Patrice.|date=1992|url=https://www.worldcat.org/oclc/26033061|title=Algorithmique algébrique : avec exercices corrigés|location=Paris|publisher=Masson|isbn=2-225-82703-6|others=Quitté, Claude.|oclc=26033061}}</ref>
 
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.
Modulo kongruensi {{mvar | n}} adalah [[relasi kekongruenan]], artinya ini adalah [[relasi ekuivalensi]] yang kompatibel dengan operasi [[penambahan]], [[pengurangan]], dan [[perkalian]]. Modulo kongruensi {{mvar | n}} dilambangkan:
 
Aritmetika modular awalnya diterapkan kepada bilangan bulat, lalu ke polinomial, dilanjutkan kepada himpunan bilangan baru yang sekarang disebut dengan [[bilangan Gaussian]].
:<math>a \equiv b \pmod n.</math>
 
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.
Tanda kurung berarti bahwa {{math|(mod ''n'')}} berlaku untuk seluruh persamaan, tidak hanya di ruas kanan (di sini {{mvar | b}}). Notasi ini jangan disamakan dengan notasi {{math|''b'' mod ''n''}} (tanpa tanda kurung), yang mengacu pada [[operasi modulo]]. Maka, {{math|''b'' mod ''n''}} menunjukkan bilangan bulat unik {{mvar | a}} sehingga {{math|0 ≤ ''a'' < ''n''}} dan <math>a \equiv b \; (\text{mod}\; n)</math> (misalnya sisa <math>b</math> jika 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>).
 
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 -->
Hubungan kongruensi dapat ditulis ulang sebagai
:<math>a = kn + b,</math>
secara eksplisit menunjukkan hubungannya dengan [[pembagian Euklides]]. Namun, {{math | '' b ''}} tidak menjadi sisa dari pembagian {{math | '' a ''}} oleh {{math | '' n ''.}} Sebagai gantinya, pernyataan {{math|''a'' ≡ ''b'' (mod ''n'')}} bahwa {{math | '' a ''}} dan {{math | '' b ''}} memiliki sisa yang sama jika dibagi dengan {{math | '' n ''}} adalah,
:<math>a = pn + r,</math>
:<math>b = qn + r,</math>
dimana {{math|0 ≤ ''r'' < ''n''}} adalah sisa umum. Dengan mengurangkan dua ekspresi ini, kami memulihkan hubungan sebelumnya:
:<math>a - b = kn,</math>
dengan menyetel {{math|1 = ''k'' = ''p'' − ''q''.}}
 
=== ContohAbad ke-20 ===
Dalam modulus 12, seseorang dapat menyatakan bahwa:
 
==== Kriptografi ====
:<math>38 \equiv 14 \pmod {12}</math>
[[Berkas:Enigma.jpg|jmpl|''[[Mesin Enigma|Enigma]]'' adalah mesin enkripsi yang digunakan selama [[Perang Dunia II]], berhasil dipecahkan oleh matematikawan [[Marian Rejewski]].]]
[[Kriptografi]] adalah ilmu yang mempelajari sandi rahasia, dan awalnya termasuk dalam [[matematika murni]]. Di sisi lain, aplikasi pada bidang industri yang meningkat membuat notasi matematika yang dikembangkan Gauss populer digunakan dalam ilmu ini. Pada tahun 1883, [[Auguste Kerckhoffs]] menyatakan bahwa "keamanan sistem kriptografi seharusnya tidak didasarkan pada kerahasiaan [[Algoritme|algoritma]] yang digunakan. Keamanan seharusnya hanya bergantung pada kerahasiaan [[Kunci (kriptografi)|kunci]]."<ref>{{Cite journal|last=Kerckhoffs|first=A.|date=1883|title=La cryptographie militaire|url=http://www.petitcolas.net/fabien/kerckhoffs|journal=Journal des sciences militaires|volume=IX|issue=|pages=5-83 dan 161-191|doi=}}</ref> Pendekatan baru ini memodifikasi bentuk ilmu ini. Pada pertengahan abad ke-20, ilmu ini menjadi cabang dari [[matematika terapan]].<ref>{{Cite journal|last=Shannon|first=Claude|date=1949|title=Communication Theory of Secrecy Systems|url=|journal=Bell System Technical Journal|volume=29|issue=|pages=656-715|doi=}}</ref>
 
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 objek matematika tersebut --> Istilah "aritmatika modular" digunakan untuk menjelaskan teknik ini.<!-- belum semuanya dialihbahasakan -->
karena {{math | 38 - 14 {{=}} 24}}, yang merupakan kelipatan 12. Cara lain untuk menyatakannya adalah dengan mengatakan bahwa 38 dan 14 memiliki sisa 2 yang sama, jika dibagi 12.
 
==== Teori informasi ====
Definisi kongruensi juga berlaku untuk nilai negatif. Sebagai contoh:
{{See also|teori informasi}}
[[Berkas:P-MMX.JPG|jmpl|[[Pentium|Prosesor Pentium]] berisi perintah aritmetika dan unit logika yang didasarkan pada aritmetika modular.]]
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 pengkodean sederhana seperti ''checksum''. Pada tahun 1960, [[Kode siklik|pengkodean]] 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=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.
:<math> \begin{align}
2 &\equiv -3 \pmod 5\\
-8 &\equiv 7 \pmod 5\\
-3 &\equiv -8 \pmod 5.
\end{align}</math>
 
Teknik yang dikembangkan untuk kriptografi, [[teori kode]], dan aritmetika komputer, didasarkan pada konsep yang sama, memberikan suatu kesatuan di matematika terkait teori informasi.
== Sifat ==
Relasi kesesuaian memenuhi semua kondisi dari [[relasi ekuivalen]]si:
* Refleksivitas: {{math|''a'' ≡ ''a'' (mod ''n'')}}
* Simetri: {{math|''a'' ≡ ''b'' (mod ''n'')}} jika {{math|''b'' ≡ ''a'' (mod ''n'')}} untuk {{math|''a''}}, {{math|''b''}}, dan {{math|''n''}}.
* Transitivitas: Jika {{math|''a'' ≡ ''b'' (mod ''n'')}} dan {{math|''b'' ≡ ''c'' (mod ''n'')}}, maka {{math|''a'' ≡ ''c'' (mod ''n'')}}
 
== Objek dengan aritmetika modular ==
Jika {{math|''a''<sub>1</sub> ≡ ''b''<sub>1</sub> (mod ''n'')}} dan {{math|''a''<sub>2</sub> ≡ ''b''<sub>2</sub> (mod ''n''),}} atau jika {{math|''a'' ≡ ''b'' (mod ''n''),}} maka:
* {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}} untuk bilangan bulat {{math|''k''}} (kompatibilitas dengan translasi)
* {{math|''k a'' ≡ ''k b'' (mod ''n'')}} untuk bilangan bulat {{math|''k''}} (kompatibilitas dengan penskalaan)
* {{math|''a''<sub>1</sub> + ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> + ''b''<sub>2</sub> (mod ''n'')}} (kompatibilitas dengan tambahan)
* {{math|''a''<sub>1</sub> – ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> – ''b''<sub>2</sub> (mod ''n'')}} (kompatibilitas dengan pengurangan)
* {{math|''a''<sub>1</sub> ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> ''b''<sub>2</sub> (mod ''n'')}} (kompatibilitas dengan perkalian)
* {{math|''a''<sup>''k''</sup> ≡ ''b''<sup>''k''</sup> (mod ''n'')}} untuk bilangan bulat non-negatif {{math | '' k ''}} (kompatibilitas dengan eksponen)
* {{math|''p''(''a'') ≡ ''p''(''b'') (mod ''n'')}}, untuk [[polinomial]] {{math|''p''(''x'')}} dengan koefisien integer (kompatibilitas dengan evaluasi polinomial)
 
=== Kekongruenan bilangan bulat ===
Jika {{math|''a'' ≡ ''b'' (mod ''n'')}}, maka umumnya {{math|''k<sup>a</sup>'' ≡ ''k<sup>b</sup>'' (mod ''n'')}}. Namun, hal berikut ini benar:
{{See also|operasi modulus}}
* Jika {{math|''c'' ≡ ''d'' (mod ''φ''(''n'')),}} dengan {{math | '' φ ''}} adalah [[fungsi total Euler]], lalu asalkan {{math | '' a ''}} [[Koprima (bilangan)|koprima]] dengan {{math | '' n ''}}-{{math|''a''<sup>''c''</sup> ≡ ''a''<sup>''d''</sup> (mod ''n'')}}.
Penerapan aritmetika modular tertua ada pada [[bilangan 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''. Dua bilangan bulat dikatakan '''kongruen''' modulo{{mvar | n}}, jika selisih kedua bilangan tersebut merupakan kelipatan{{mvar | n}} (yaitu, jika ada bilangan bulat {{math | '' k ''}} sehingga {{math|1=''a'' − ''b'' = ''kn''}}).
 
Kekongruenan modulo ''n'' adalah sebuah [[relasi kekongruenan]], artinya kekongruenan adalah [[relasi ekuivalensi]] yang kompatibel dengan operasi [[penambahan]], [[pengurangan]], dan [[perkalian]]. Kekongruenan modulo{{mvar | n}} dilambangkan:
Untuk pembatalan istilah umum, kami memiliki aturan berikut:
 
:<math>a \equiv b \pmod n.</math>
* Jika {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}}, dengan {{math | '' k ''}} adalah sembarang bilangan bulat, lalu {{math|''a'' ≡ ''b'' (mod ''n'')}}
* Jika {{math|''k a'' ≡ ''k b'' (mod ''n'')}} dan {{math | '' k ''}} koprima dengan {{math | '' n ''}}, maka {{math|''a'' ≡ ''b'' (mod ''n'')}}
* Jika {{math|''k a'' ≡ ''k b'' (mod ''kn'')}}, maka {{math|''a'' ≡ ''b'' (mod ''n'')}}
 
Tanda kurung mengartikan bahwa {{math|(mod ''n'')}} berlaku untuk kedua ruas persamaan. Notasi ini berbeda dengan notasi {{math|''b'' mod ''n''}} (tanpa tanda kurung), yang mengacu pada [[operasi modulus]]. Notasi {{math|''b'' mod ''n''}} merujuk pada sebuah bilangan bulat unik <math>a</math> dengan <math>0 \leq a < n</math> dan memenuhi <math>a \equiv b \; (\text{mod}\; n)</math> (Dengan kata lain, sisa <math>b</math> ketika 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>).
[[Perkalian modular invers]] ditentukan oleh aturan berikut:
* Eksistensi: ada bilangan bulat yang dilambangkan {{math|''a''<sup>–1</sup>}} seperti {{math|''aa''<sup>–1</sup> ≡ 1 (mod ''n'')}} jika dan hanya jika {{math | '' a ''}} sesuai dengan {{math | '' n ''}}. Bilangan bulat {{math|''a''<sup>–1</sup>}} disebut '' perkalian modular invers '' dari {{mvar | a}} modulo {{math|''n''}}.
* Jika {{math|''a'' ≡ ''b'' (mod ''n'')}} dan {{math|''a''<sup>–1</sup>}}, maka {{math|''a''<sup>–1</sup> ≡ ''b''<sup>–1</sup> (mod ''n'')}} (kompatibilitas dengan pembalikan perkalian, dan jika {{math|1=''a'' = ''b''}}, modulo {{math | '' n ''}})
* Jika {{math|''a x'' ≡ ''b'' (mod ''n'')}} dan {{math | '' a ''}} koprima dengan {{math | '' n ''}}, maka solusi untuk kongruensi linear ini diberikan oleh {{math|''x'' ≡ ''a''<sup>–1</sup>''b'' (mod ''n'')}}
 
Sebagai contoh, dalam modulus 12 seseorang dapat menyatakan bahwa <math>38 \equiv 14 \ \ (\text{mod}\ \ 12)</math>, karena {{math | 38 - 14 {{=}} 24}} merupakan kelipatan 12. Cara lain untuk menyatakannya adalah dengan mengatakan bahwa 38 dan 14 memiliki sisa yang sama, yakni 2, ketika dibagi dengan 12.
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]].
 
Himpunan {{math|&#123;… , ''a'' − 2''n'', ''a'' − ''n'', ''a'', ''a'' + ''n'', ''a'' + 2''n'', …&#125;}} adalah himpunan semua bilangan bulat yang kongruen dengan ''a'' modulo ''n''. Himpunan ini disebut ''kelas kekongruenan'', ''kelas residu'', atau cukup dengan ''residu'' dari ''a'' modulo ''n''; dan dilambangkan dengan {{math|{{overline|''a''}}{{sub|''n''}}}}. Gauss berkontribusi dengan menganalisis struktur himpunan kelas kekongruenan ini, yang sekarang dikenal dengan ''gelanggang bilangan bulat modulo {{math |''n''}}'',<ref>Ini adalah [[Gelanggang (matematika)|gelanggang]], ditunjukkan di bawah.</ref> dan dilambangkan <math display="inline">\mathbb{Z}/n\mathbb{Z}</math>, <math>\mathbb{Z}/n</math>, atau <math>\mathbb{Z}_n</math>.<ref name=":0" /><ref>{{Cite web|date=2013-11-16|title=2.3: Integers Modulo n|url=https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Book%3A_Introduction_to_Algebraic_Structures_(Denton)/02%3A_Groups_I/2.03%3A_Integers_Modulo_n|website=Mathematics LibreTexts|language=en|access-date=2020-08-12}}</ref> Namunn, notasi <math>\mathbb{Z}_n</math> tidak disarankan karena bisa disalahartikan dengan himpunan [[P-adik#Pendekatan Aljabar|bilangan bulat adic-{{math | '' n ''}}]]. Gelanggang <math>\mathbb{Z}/n\mathbb{Z}</math> fundamental untuk berbagai cabang matematika (lihat {{section link|#Aplikasi}} di bawah).
Secara khusus, jika {{math | '' p ''}} adalah bilangan prima, maka {{math | '' a ''}} coprima dengan {{math | '' p ''}} untuk {{math | '' a ''}} sehingga {{math|0 < ''a'' < ''p''}}; sehingga invers perkalian ada untuk semua {{math | '' a ''}} yang tidak kongruen dengan nol modulo {{math | '' p ''}}.
 
[[Gelanggang (matematika)|Gelanggang]] ini didefinisikan untuk '' n ''> 0 sebagai:
Beberapa properti lanjutan dari hubungan kesesuaian adalah sebagai berikut:
 
* [[Teorema kecil Fermat]]: Jika {{math | '' p ''}} adalah bilangan prima dan tidak membagi {{math | '' a ''}}, maka {{math|''a'' <sup>''p'' – 1</sup> ≡ 1 (mod ''p'')}}.
:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{a}_n \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n{-}1}_n \right\}.</math>
* [[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'')}}.
Operasi penjumlahan, pengurangan, dan perkalian di <math>\mathbb{Z}/n\mathbb{Z}</math> adalah analogi dari kekongruenan bilangan bulat:
* Konsekuensi sederhana lainnya adalah jika {{math|''a'' ≡ ''b'' (mod ''φ''(''n'')),}} dengan {{math | '' φ ''}} adalah fungsi total Euler, maka {{math|''k''<sup>''a''</sup> ≡ ''k''<sup>''b''</sup> (mod ''n'')}} asalkan {{math | '' k ''}} adalah [[coprime|koprima]] dengan {{math | '' n ''}}.
 
* [[Teorema Wilson]]: {{math|''p''}} is prime if and only if {{math|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* <math>\overline{a}_n + \overline{b}_n = \overline{(a + b)}_n</math>
* [[Teorema sisa Cina]]: Untuk {{math | '' a ''}}, {{math | '' b ''}}, dan koprima {{math | '' m ''}}, {{math | ' 'n' '}}, maka {{math|''x'' (mod ''mn'')}} seperti {{math|''x'' ≡ ''a'' (mod ''m'')}} dan {{math|''x'' ≡ ''b'' (mod ''n'')}}. Faktanya, {{math|''x'' ≡ ''b m''<sub>''n''</sub><sup>–1</sup> ''m'' + ''a n''<sub>''m''</sub><sup>–1</sup> ''n'' (mod ''mn'')}} dimana {{math|''m''<sub>''n''</sub><sup>−1</sup>}} adalah kebalikan dari {{math | '' m ''}} modulo {{math | '' n ''}} dan {{math|''n''<sub>''m''</sub><sup>−1</sup>}} adalah kebalikan dari {{math | '' n ''}} modulo {{math | '' m ''}}.
* <math>\overline{a}_n - \overline{b}_n = \overline{(a - b)}_n</math>
* [[Teorema Lagrange (teori bilangan)|Teorema Lagrange]]: Kesesuaian {{math|''f'' (''x'') ≡ 0 (mod ''p'')}}, dengan {{math | '' p ''}} adalah bilangan prima, dan {{math|''f'' (''x'') {{=}} ''a''<sub>0</sub> ''x''<sup>''n''</sup> + ... + ''a''<sub>''n''</sub>}} adalah [[polinomial]] dengan koefisien bilangan bulat {{math|''a''<sub>0</sub> &ne; 0 (mod ''p'')}}, memiliki akar {{math | '' n ''}}.
* <math>\overline{a}_n \overline{b}_n = \overline{(ab)}_n.</math>
* [[Akar primitif modulo n]]: Bilangan {{math | '' g ''}} adalah akar primitif modulo {{math | '' n ''}}, untuk bilangan bulat {{math | '' a '' }} koprima dengan {{math | '' n ''}}, bilangan bulat {{math | '' k ''}} adalah {{math|''g''<sup>''k''</sup> ≡ ''a'' (mod ''n'')}}. Sebuah root modulo {{math | '' n ''}} ada jika dan hanya jika {{math | '' n ''}} sama dengan {{math|2, 4, ''p''<sup>''k''</sup>}} atau {{math| 2''p''<sup>''k''</sup>}}, dengan {{math | '' p ''}} adalah bilangan prima ganjil dan {{math | '' k ''}} adalah bilangan bulat positif. Jika aka4 modulo {{math | '' n ''}} primitif ada, maka persis ada {{math|''φ''(''φ''(''n''))}} akar primitif, di mana {{math | '' φ ''}} adalah fungsi total Euler.
 
* [[Residu kuadrat]]: Bilangan bulat {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' n ''}}, jika terdapat bilangan bulat {{math | '' x ''}} seperti yang {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''n'')}}. [[Kriteria Euler]] menegaskan bahwa, jika {{math | '' p ''}} adalah bilangan prima ganjil, dan {{mvar | a}} bukan kelipatan {{mvar | p}}, maka {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' p ''}} jika dan hanya jika
Dalam hal ini, <math>\mathbb{Z}/n\mathbb{Z}</math> adalah [[gelanggang komutatif]]. Misalnya, di gelanggang <math>\mathbb{Z}/24\mathbb{Z}</math>, dapat ditulis
::<math>a^{(p-1)/2} \equiv 1 \pmod p.</math>
:<math>\overline{12}_{24} + \overline{21}_{24} = \overline{33}_{24}= \overline{9}_{24}</math>
seperti dalam aritmetika modular untuk sistem 24 jam.
 
=== Polinomial ===
{{Main|polinomial siklotomik}}
[[Berkas:Heptadecagone.jpg|jmpl|Konstruksi dengan penggaris dan jangka dari poligon reguler 17 sisi, dengan menggunakan teknik aritmatika modular.]]
Gauss menyadari aritmetika modular juga dapat diterapkan pada himpunan [[polinomial]] dengan koefisien [[bilangan pecahan]], karena himpunan tersebut memiliki penjumlahan, perkalian, dan pembagian Euklides. Kekongruenan pada himpunan ini didasarkan dari sisa hasil bagi Euklides sebuah polinomial dengan polinomial lain.
 
Gauss menerapkan pendekatan ini ke polinomial <math>x^n-1</math> dan menemukan [[Faktorisasi|faktor-faktor primitifnya]], yang disebut dengan ''polinomial siklotomik''. Hal ini digunakan untuk menemukan konstruksi penggaris dan jangka dari [[heptadekagon]], sebuah poligon reguler dengan 17 sisi. Namun, ia ragu untuk menganggap penerapan ini termasuk dalam aritmetika; ia menulis: "Teori pembagian pada lingkaran, atau pada poligon reguler ..., bukan bagian dari aritmetika dengan sendirinya, namun prinsipnya didapatkan dari aritmetika tingkat lanjut".<ref>[[Carl Friedrich Gauss]] (<abbr>trad.</abbr> A.-C.-M. Poullet-Delisle, éd. Courcier, 1807), [ [[Disquisitiones Arithmeticae]] ], 1801</ref>
 
=== Bilangan aljabar ===
== Kelas kongruensi {{Anchor|Residu | Kelas residu | Kelas kongruensi}} ==
{{Main|Bilangan Gaussian}}
Seperti relasi kesesuaian lainnya, kongruensi modulo {{math | '' n ''}} adalah [[relasi ekuivalensi]], dan [[ekuivalen]] dari bilangan bulat {{math | '' a ''}}, dilambangkan dengan {{math|{{overline|''a''}}{{sub|''n''}}}}, adalah himpunan {{math|&#123;… , ''a'' − 2''n'', ''a'' − ''n'', ''a'', ''a'' + ''n'', ''a'' + 2''n'', …&#125;}}. Himpunan ini, terdiri dari semua bilangan bulat yang kongruen dengan {{math|''a''}}&nbsp;modulo&nbsp;{{math|''n''}}, disebut '''kelas kongruensi''', '''kelas residu''', atau hanya '''residu''' dari bilangan bulat {{math|''a''}} modulo&nbsp;{{math|''n''}}. Ketika modulus {{math | '' n ''}} diketahui dari konteksnya, residu ini dilambangkan {{math|[''a'']}}.
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 ===
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>
 
Himpunan bilangan bulat {{math|&#123;0, 1, 2, …, ''n'' − 1&#125;}} disebut '''modulo sistem residu terkecil {{math |' 'n' '}}'''. Setiap rangkaian bilangan bulat {{math | '' n ''}}, tidak ada dua yang kongruen modulo {{math | '' n ''}}, disebut '''modulo sistem residu lengkap {{math |' 'n' '}}'''.
Baris 121 ⟶ 117:
*{5, 15}, karena modulo 4 sistem residu lengkap harus memiliki tepat 4 kelas residu yang tidak selaras.<!-- Contoh ini digunakan dalam sub-bagian berikut jadi jangan mengubahnya. -->
 
==== Sistem residu berkurang ====
{{Main|Mengurangi sistem residu}}
[[Fungsi total Euler]] {{math|φ(''n'')}}, himpunan dari {{math|φ(''n'')}} bilangan bulat yang [[Coprime integers|relative prime]] menjadi {{math | '' n ''}} dan saling tidak selaras di bawah modulus {{math | '' n ''}} disebut '''modulo sistem residu tereduksi {{matematika | '' n ''}}'''.<ref>{{harvtxt|Long|1972|p=85}}</ref> Himpunan {5,15} dari atas, misalnya, adalah turunan dari modulo 4 sistem residu tereduksi.
 
== Perkembangan teoritis ==
== Bilangan bulat modulo '' n '' ==
Dalam matematika, umum dijumpai sebuah konsep matematika yang dikembangkan dalam sebuah bidang, digunakan ulang pada bidang-bidang lain. Hal yang sama juga berlaku untuk aritmetika modular, yang membantu banyak bidang [[matematika murni]], seperti [[aljabar]] dan [[teori Galois]]. Namun, perkembangan-perkembangan berikut tidak dianggapkan sebagai kasus khusus dari aritmetika modular, karena digunakan bersama konsep-konsep lainnya.
Himpunan dari semua [[Modular aritmatika#Kelas kesesuaian|kelas kongruensi]] dari bilangan bulat untuk modulus {{math | '' n ''}} disebut '''gelanggang bilangan bulat modulo {{math |''n''}} ''',<ref>Ini adalah [[gelanggang (matematika)|gelanggang]], ditunjukkan di bawah.</ref> dan dilambangkan <math display=inline>\mathbb{Z}/n\mathbb{Z}</math>, <math>\mathbb{Z}/n</math>, atau <math>\mathbb{Z}_n</math>.<ref name=":0" /><ref>{{Cite web|date=2013-11-16|title=2.3: Integers Modulo n|url=https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Book%3A_Introduction_to_Algebraic_Structures_(Denton)/02%3A_Groups_I/2.03%3A_Integers_Modulo_n|access-date=2020-08-12|website=Mathematics LibreTexts|language=en}}</ref> Notasi <math>\mathbb{Z}_n</math> adalah, bagaimanapun, tidak disarankan karena bisa disalahartikan dengan himpunan [[P-adik#Pendekatan Aljabar|bilangan bulat adic-{{math | '' n ''}}]]. Gelanggang <math>\mathbb{Z}/n\mathbb{Z}</math> adalah fundamental untuk berbagai cabang matematika (lihat {{section link|#Aplikasi}} di bawah).
 
=== Struktur hasil bagi ===
Himpunan ditentukan untuk '' n ''> 0 sebagai:
{{Main|relasi ekuivalensi}}
Dalam matematika modern, aritmetika modular diformalkan dengan menggunakan konsep ''Euclidean ring''. Konsep [[relasi ekuivalensi]] memungkinkan aritmetika modular diterapkan ke banyak [[struktur aljabar]]. Sebagai contoh, [[Grup hasil bagi|hasil bagi]] sebuah [[Grup (matematika)|grup]] dengan sebuah [[subgrup normal]], dengan menggunakan [[teorema Jordan-Holder]], adalah alat dasar untuk mengklasifikasikan [[grup hingga]]. Grup hasil bagi juga digunakan dalam [[topologi aljabar]] untuk mengelompokkan [[Lipatan (matematika)|lipatan]].
 
== Sifat kekongruenan bilangan bulat ==
:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{a}_n \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n{-}1}_n \right\}.</math>
{{See also|Relasi kekongruenan|Operasi modulus}}Hubungan kekongruenan bilangan bulat dapat ditulis sebagai
:<math>a = kn + b,</math>
yang secara eksplisit menunjukkan hubungannya dengan [[pembagian Euklides]]. Namun, suku <math>b</math> tersebut bukanlah sisa pembagian <math>a</math> oleh <math>n</math>. Dalam pengartian yang lebih tepat, <math>a \equiv b \ \ (\text{mod}\, n)</math> bahwa {{math | '' a ''}} dan {{math | '' b ''}} memiliki sisa yang sama ketika dibagi dengan{{math | '' n ''}}, yakni
:<math>a = pn + r,</math>
:<math>b = qn + r,</math>
dengan {{math|0 ≤ ''r'' < ''n''}} adalah sisa pembagian keduanya. Mengurangkan kedua ekspresi diatas, kita dapat menemukan hubungan <math>a - b = kn</math> sebelumnya, dengan memilih {{math|1 = ''k'' = ''p'' − ''q''.}}
 
Definisi kekongruenan juga berlaku untuk nilai negatif. Sebagai contoh:
(Maka {{math|''n'' {{=}} 0}}, <math>\mathbb{Z}/n\mathbb{Z}</math> bukan merupakan [[himpunan kosong]]; sebaliknya, [[isomorfisme|isomorfik]] menjadi <math>\mathbb{Z}</math>, maka {{math|{{overline|''a''}}{{sub|0}} {{=}} &#123;''a''&#125;}}.)
:<math> \begin{align}
2 &\equiv -3 \pmod 5\\
-8 &\equiv 7 \pmod 5\\
-3 &\equiv -8 \pmod 5.
\end{align}</math>
 
=== Sifat dasar ===
Kami mendefinisikan penjumlahan, pengurangan, dan perkalian di <math>\mathbb{Z}/n\mathbb{Z}</math> dengan aturan berikut:
Relasi kekongruenan pada bilangan bulat memenuhi semua kondisi [[relasi ekuivalensi]]. Dengan demikian, pada relasi kekongruenan <math>\equiv</math> modulo <math>n</math> berlaku
* Sifat refleksif: <math>a \equiv a</math>
* Sifat simetris: jika <math>a \equiv b</math> maka <math>b \equiv a</math>
* Sifat transitif: jika <math>a \equiv b</math> dan <math>b \equiv c</math>, maka <math>a \equiv c</math>
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>
Untuk operasi pencoretan (pembatalan) berlaku aturan berikut:
* Bentuk <math>a+k \equiv b+k</math> dapat disederhanakan menjadi <math>a \equiv b</math>
*Bentuk <math>ak \equiv bk \pmod{kn}</math> dapat disederhanakan menjadi <math>a \equiv b \pmod{n}</math>
* Untuk kasus <math>k</math> dan <math>n</math> saling koprima, bentuk <math>ak \equiv bk \pmod{n}</math> dapat disederhanakan menjadi <math>a \equiv b \pmod{n}</math>
 
Jika <math>a \equiv b \pmod{n}</math>, belum tentu berlaku <math>k^a \equiv k^b \pmod n</math>. Hal tersebut hanya berlaku jika <math>k</math> koprima dengan <math>n</math> dan <math>a \equiv b \pmod{\varphi(n)}</math>, dengan {{math | '' φ ''}} adalah [[fungsi total Euler]].
* <math>\overline{a}_n + \overline{b}_n = \overline{(a + b)}_n</math>
* <math>\overline{a}_n - \overline{b}_n = \overline{(a - b)}_n</math>
* <math>\overline{a}_n \overline{b}_n = \overline{(ab)}_n.</math>
 
=== Invers perkalian ===
Verifikasi bahwa ini adalah definisi yang tepat menggunakan properti yang diberikan sebelumnya.
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.
* Jika <math>ax \equiv b</math> dan <math>a^{-1}</math> ada, maka solusi untuk kekongruenan linear tersebut adalah <math>x \equiv a^{-1}b</math>
 
Invers perkalian invers <math>x \equiv a^{-1} \pmod n</math> dapat cari secara efisien dengan menemukan nilai <math> x, y </math> pada [[identitas Bézout|Persamaan Bézout]] <math> ax + ny = 1 </math>; dengan menggunakan [[algoritme Euklides diperluas]].
Maka, <math>\mathbb{Z}/n\mathbb{Z}</math> menjadi [[gelanggang komutatif]]. Misalnya, di gelanggang <math>\mathbb{Z}/24\mathbb{Z}</math>, maka
:<math>\overline{12}_{24} + \overline{21}_{24} = \overline{33}_{24}= \overline{9}_{24}</math>
seperti dalam aritmatika untuk sistem 24 jam.
 
=== Sifat lain ===
Kami menggunakan notasi <math>\mathbb{Z}/n\mathbb{Z}</math> karena ini adalah [[gelanggang hasil bagi]] dari <math>\mathbb{Z}</math> oleh [[gelanggang ideal|ideal]] <math>n\mathbb{Z}</math>, satu set yang berisi semua bilangan bulat habis dibagi oleh {{math | '' n ''}}, di mana <math>0\mathbb{Z}</math> adalah [[himpunan singleton]] {{math|&#123;0&#125;}}. Jadi <math>\mathbb{Z}/n\mathbb{Z}</math> adalah [[Bidang (matematika)|bidang]] <math>n\mathbb{Z}</math> adalah [[ideal maksimal]] (yaitu, jika {{math | '' n ''}} adalah bilangan prima).
Berikut daftar beberapa hasil lebih lanjut terkait hubungan kekongruenan:
* [[Teorema kecil Fermat]]: Jika {{math | '' p ''}} adalah bilangan prima yang tidak membagi {{math | '' a ''}}, maka {{math|''a'' <sup>''p'' – 1</sup> ≡ 1 (mod ''p'')}}.
* [[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'')}}.
* Konsekuensi sederhana lainnya adalah jika {{math|''a'' ≡ ''b'' (mod ''φ''(''n'')),}} dengan {{math | '' φ ''}} adalah fungsi total Euler, maka {{math|''k''<sup>''a''</sup> ≡ ''k''<sup>''b''</sup> (mod ''n'')}} asalkan {{math | '' k ''}} adalah [[coprime|koprima]] dengan {{math | '' n ''}}.
* [[Teorema Wilson]]: {{math|''p''}} is prime if and only if {{math|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* [[Teorema sisa Cina]]: Untuk {{math | '' a ''}}, {{math | '' b ''}}, dan koprima {{math | '' m ''}}, {{math | ' 'n' '}}, maka {{math|''x'' (mod ''mn'')}} seperti {{math|''x'' ≡ ''a'' (mod ''m'')}} dan {{math|''x'' ≡ ''b'' (mod ''n'')}}. Faktanya, {{math|''x'' ≡ ''b m''<sub>''n''</sub><sup>–1</sup> ''m'' + ''a n''<sub>''m''</sub><sup>–1</sup> ''n'' (mod ''mn'')}} dimana {{math|''m''<sub>''n''</sub><sup>−1</sup>}} adalah kebalikan dari {{math | '' m ''}} modulo {{math | '' n ''}} dan {{math|''n''<sub>''m''</sub><sup>−1</sup>}} adalah kebalikan dari {{math | '' n ''}} modulo {{math | '' m ''}}.
* [[Teorema Lagrange (teori bilangan)|Teorema Lagrange]]: Kesesuaian {{math|''f'' (''x'') ≡ 0 (mod ''p'')}}, dengan {{math | '' p ''}} adalah bilangan prima, dan {{math|''f'' (''x'') {{=}} ''a''<sub>0</sub> ''x''<sup>''n''</sup> + ... + ''a''<sub>''n''</sub>}} adalah [[polinomial]] dengan koefisien bilangan bulat {{math|''a''<sub>0</sub> &ne; 0 (mod ''p'')}}, memiliki akar {{math | '' n ''}}.
* [[Akar primitif modulo n]]: Bilangan {{math | '' g ''}} adalah akar primitif modulo {{math | '' n ''}}, untuk bilangan bulat {{math | '' a '' }} koprima dengan {{math | '' n ''}}, bilangan bulat {{math | '' k ''}} adalah {{math|''g''<sup>''k''</sup> ≡ ''a'' (mod ''n'')}}. Sebuah root modulo {{math | '' n ''}} ada jika dan hanya jika {{math | '' n ''}} sama dengan {{math|2, 4, ''p''<sup>''k''</sup>}} atau {{math| 2''p''<sup>''k''</sup>}}, dengan {{math | '' p ''}} adalah bilangan prima ganjil dan {{math | '' k ''}} adalah bilangan bulat positif. Jika aka4 modulo {{math | '' n ''}} primitif ada, maka persis ada {{math|''φ''(''φ''(''n''))}} akar primitif, di mana {{math | '' φ ''}} adalah fungsi total Euler.
* [[Residu kuadrat]]: Bilangan bulat {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' n ''}}, jika terdapat bilangan bulat {{math | '' x ''}} seperti yang {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''n'')}}. [[Kriteria Euler]] menegaskan bahwa, jika {{math | '' p ''}} adalah bilangan prima ganjil, dan {{mvar | a}} bukan kelipatan {{mvar | p}}, maka {{math | '' a ''}} adalah modulo residu kuadrat {{math | '' p ''}} jika dan hanya jika
::<math>a^{(p-1)/2} \equiv 1 \pmod p.</math>
 
== Aplikasi ==
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 264 ⟶ 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.&nbsp;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}}
 
== Pranala luar ==
* {{springer|title=Congruence|id=p/c024850}}
* Dalam [https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm modular art] artikel, seseorang dapat mempelajari lebih lanjut tentang aplikasi aritmatika modular dalam seni.
* An [https://web.archive.org/web/20160220061222/http://mersennewiki.org/index.php/Modular_arithmetic article] tentang aritmatika modular di wiki GIMPS
Diperoleh dari "https://wiki-indonesia.club/wiki/Aritmetika_modular"