Aritmetika modular: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Menambah teks pada →Sejarah: , hasil alih bahasa dari artikel Wikipedia Bahasa Perancis fr: Arithmétique modulaire; Lihat sejarahnya untuk atribusi. Merapikan susunan bagian tulisan |
Menambahkan →Sejarah: , hasil alih bahasa dari artikel Wikipedia Bahasa Perancis fr: Arithmétique modulaire; Lihat sejarahnya untuk atribusi. menambah penjelasan pada bagian pembuka. menyusun kembali posisi sub-subbagian untuk mempermudah pengembangan artikel |
||
Baris 2:
[[Berkas:Clock group.svg|thumb|250px|right|Pengatur waktu pada jam ini menggunakan aritmatika 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]].
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 ==
Baris 22 ⟶ 24:
=== 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>.
=== <!-- Perkembanga metode yang digunakan --> ===
===
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 menulis pembuktian yang lebih sederhana, walau menjadi lebih abstrak. Pendekatannya adalah dasar bagi aritmetika modular.<!-- belum semuanya dialihbahasakan -->
=== Abad ke-20 ===
==== Kriptografi ====
[[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 <!-- tolong koreksi --> atas bilangan bulat. Istilah "aritmatika modular" digunakan untuk menjelaskan teknik ini.<!-- belum semuanya dialihbahasakan -->
== Objek dengan aritmetika modular ==
=== Kekongruenan bilangan bulat ===
{{See also|operasi modulus}}
[[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''}}).
Baris 50 ⟶ 61:
dengan menyetel {{math|1 = ''k'' = ''p'' − ''q''.}}
Contoh, Dalam modulus 12, seseorang dapat menyatakan bahwa:
:<math>38 \equiv 14 \pmod {12}</math>
Baris 65 ⟶ 75:
\end{align}</math>
Himpunan dari semua [[Modular aritmatika#Kelas kesesuaian|kelas kekongruenan]] 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|website=Mathematics LibreTexts|language=en|access-date=2020-08-12}}</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).
Himpunan ditentukan untuk '' n ''> 0 sebagai:
:<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>
(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}} {{=}} {''a''}}}.)
Kami mendefinisikan penjumlahan, pengurangan, dan perkalian di <math>\mathbb{Z}/n\mathbb{Z}</math> dengan aturan berikut:
* <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>
Verifikasi bahwa ini adalah definisi yang tepat menggunakan properti yang diberikan sebelumnya.
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.
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|{0}}}. 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).
=== Kelas kekongruenan ===
Seperti relasi kesesuaian lainnya, kekongruenan modulo {{math | '' n ''}} adalah [[relasi ekuivalensi]], dan [[ekuivalen]] dari bilangan bulat {{math | '' a ''}}, dilambangkan dengan {{math|{{overline|''a''}}{{sub|''n''}}}}, adalah himpunan {{math|{… , ''a'' − 2''n'', ''a'' − ''n'', ''a'', ''a'' + ''n'', ''a'' + 2''n'', …}}}. Himpunan ini, terdiri dari semua bilangan bulat yang kongruen dengan {{math|''a''}} modulo {{math|''n''}}, disebut '''kelas kekongruenan''', '''kelas residu''', atau hanya '''residu''' dari bilangan bulat {{math|''a''}} modulo {{math|''n''}}. Ketika modulus {{math | '' n ''}} diketahui dari konteksnya, residu ini dilambangkan {{math|[''a'']}}.
=== 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}}</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|{0, 1, 2, …, ''n'' − 1}}} 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' '}}'''.
Sistem residu terkecil adalah sistem residu lengkap, dan sistem residu lengkap hanyalah satu himpunan yang berisi tepat satu perwakilan dari setiap kelas residu modulo {{math | '' n ''}}.<ref>{{harvtxt|Long|1972|p=78}}</ref> Sebagai contoh. modulo 4 sistem residu terkecil adalah {0, 1, 2, 3}. Beberapa sistem residu lengkap lainnya modulo 4 meliputi:
*{1, 2, 3, 4}
*{13, 14, 15, 16}
*{−2, −1, 0, 1}
*{−13, 4, 17, 18}
*{−5, 0, 6, 21}
*{27, 32, 37, 42}
Beberapa set yang '' bukan '' sistem residu lengkap modulo 4 adalah:
*{−5, 0, 6, 22}, karena 6 kongruen dengan 22 modulo 4.
*{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.
== Sifat kekongruenan bilangan bulat ==
Relasi kekongruenan pada bilangan bulat memenuhi semua kondisi [[relasi ekuivalensi]]:
* 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'')}}
* {{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)
Baris 110 ⟶ 168:
* [[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 ==
| |||