Aritmetika modular

Artikel ini berisi tentang konsep yang menggunakan notasi "a (mod m)". Untuk operasi biner mod(a, m), lihat operasi modulus.

Pencatat waktu pada jam ini menggunakan aritmetika modulo 12. Empat jam setelah pukul 9 ialah pukul 1, sebab 13 kongruen dengan 1 dalam modulo 12.

Dalam matematika, aritmetika modular adalah sistem operasi aritmetika untuk bilangan bulat yang nilai bilangannya "berputar kembali" saat mencapai suatu nilai tertentu, yang disebut modulus. Pendekatan modern terhadap aritmetika modular dikembangkan oleh Carl Friedrich Gauss dalam buku tahun 1801 miliknya, Disquisitiones Arithmeticae.

Contoh umum dari aritmetika modular ialah jarum jam pada sistem 12 jam. Jika jarum jam sekarang berada pada angka 7, maka 8 jam kemudian, jarum jam akan pada angka 3. Berdasarkan hasil penjumlahan biasa, maka $7+8=15$, namun 15 dibaca sebagai 3 pada tampilan jam. Hal ini disebabkan karena jarum jam melakukan satu putaran setiap 12 jam dan angka jam dimulai kembali ketika jarum jam melewati 12. Dalam konteks ini, 15 dikatakan kongruen dengan 3 modulo 12, ditulis $15\equiv 3{\pmod {12}}$, sehingga $7+8\equiv 3{\pmod {12}}$.

Dengan argumentasi serupa, jika jarum jam berada pada angka 12, maka setelah 8 jam berlalu, jarum jam akan berada di angka 8. Jika waktu tunggunya menjadi dua kali lipat semula (yaitu 16 jam), maka jarum jam akan berada pada angka 4. Hal ini dapat ditulis sebagai $2\times 8\equiv 4{\pmod {12}}$. Perhatikan bahwa setelah menunggu tepat 12 jam, jarum jam akan selalu berada di posisi yang sama seperti sebelumnya, sehingga 12 berperilaku sama seperti nol, sehingga dapat disimpulkan bahwa $12\equiv 0{\pmod {12}}$.

Sejarah

Asal mula

Laman judul edisi 1621 Aritmetika karya Diofantos, diterjemahkan ke dalam bahasa Latin oleh Claude Gaspard Bachet de Méziriac.

Pada abad ke-3 SM, Euklides merumuskan fondasi-fondasi aritmetika dalam bukunya Element. Di dalamnya, terdapat sebuah lema yang umum dirujuk sebagai lema Euklides, versi awal dari teorema dasar aritmetika dan studi mengenai bilangan sempurna dalam proposisi 36 pada bukunya ke-9. 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 $4n+3$. 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?".

Qin Jiushao (1202-1261) mengembangkan teorema sisa Cina dalam risalah matematika yang ia tulis. Materi pada risalah tesebut sangat dalam; membahas sistem kekongruenan linear pada kasus modulus-modulus pada sistem tidak saling koprima. George Sarton menyatakan bahwa karyanya pada sistem kekongruenan melebihi Leonhard Euler dan Gauss. 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.

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. Persamaan Diofantin derajat dua dipelajari Brahmagupta (598 - 668). Pada abad ke-12, Bhāskara II menyempurnakan metode Chakravala.

Masa Islam abad pertengahan memegang peran ganda dalam perkembangan aritmetika: menggabungkan pengetahuan yang didapatkan di Yunani, India, Cina, dan Eropa, dan menciptakan penemuan baru. Hal ini termasuk studi mengenai sifat dari himpunan bilangan, seperti prima, sempurna, ramah (amicable), dan poligonal. Dalam konteks ini, Qusta bin Lûqâ melakukan terjemahan parsial buku Arithmetica milik Diofantos dari Alexandria, di akhir abad ke-9. Pada masa yang sama, Al-Hajjaj menerjemahkan Elemen milik Euclid. Koleganya, Al-Kharizmi (sekitar 783 - 850), menulis buku mengenai numerisasi. Terjemahan bahasa Latin dari buku ini adalah Algoritmi de numero Indorum. Tsabit bin Qurrah (836-901) mempelajari bilangan amicable dan bilangan sempurna. Ibnu Haitham (965 - 1039) melanjutkan hasil kerjanya dan menemukan teorema Wilson.

Perkembangan di Eropa

Pierre de Fermat banyak berkontribusi mengembangkan aritmetika. Sifat-sifat pembagian Euklides, dasar dari aritmetika modular, banyak digunakan oleh matematikawan saat ini.

Pada tahun 1621, Claude-Gaspard Bachet de Méziriac 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-nya, teorema jumlah dua persegi, dan teorema kecil-nya. Marin Mersenne mencari 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". Bilangan tersebut dikenal sebagai bilangan Fermat, walau sifat keprimaannya bilangan-bilangan tersebut ternyata hanya tebakan yang keliru dari Fermat. 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 $x^{2}+2y^{2}$.

Kontribusi Carl Friedrich Gauss

Carl Friedrich Gauss adalah penemu cabang matematika yang sekarang disebut aritmetika modular.

Ketika berusia 17 tahun, 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 memublikasikan Disquisitiones Arithmeticae (Penelitian tentang Aritmetika), dan dijuluki pangeran matematikawan.

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.

Aritmetika modular awalnya diterapkan kepada bilangan bulat, lalu ke polinomial, dilanjutkan kepada himpunan bilangan baru yang sekarang disebut dengan bilangan Gaussian.

Semua persamaan Diofantin Fermat sudah terselesaikan saat ini, kecuali untuk teorema terakhirnya. Beberapa konjektur baru muncul. Sebagai contoh, jika a dan b saling koprima, 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, tetapi mereka tidak mampu membuktikannnya.

Aritmetika modular juga semakin diperkaya. Dirichlet, seorang siswa Gauss membuktikan teorema aritmetic progression dengan mengembangkan konsep karakter, sekaligus memberi dasar formal untuk ilmu teori bilangan analitik.

Abad ke-20

Kriptografi

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 algoritma yang digunakan. Keamanan seharusnya hanya bergantung pada kerahasiaan kunci." Pendekatan baru ini memodifikasi bentuk ilmu ini. Pada pertengahan abad ke-20, ilmu ini menjadi cabang dari matematika terapan.

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. Istilah "aritmetika modular" digunakan untuk menjelaskan teknik ini.

Teori informasi

Lihat pula: teori informasi

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. Walau kerahasiaan adalah salah satu topik diskusi, reabilitas (keandalan) juga menjadi tema utama bidang tersebut. Richard Hamming membuat algoritma pertama pada tahun 1950. Sekali lagi, modulus bilangan buat digunakan teknik pengkodean sederhana seperti checksum. Pada tahun 1960, pengkodean yang lebih kuat dikembangkan, didasarkan pada polinomal dengan koefisien atas finite field. Aritmetika yang digunakan untuk objek tersebut umumnya menggunakan kata "modular".

Ilmu komputer menjadi kajian akademik pada awal tahun 1960. 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 kode, dan aritmetika komputer, didasarkan pada konsep yang sama, memberikan suatu kesatuan di matematika terkait teori informasi.

Kekongruenan

Diberikan bilangan bulat $n\geq 1$, yang disebut sebagai modulus, dua bilangan bulat $a$ dan $b$ dikatakan kongruen modulo $n$ jika selisih kedua bilangan tersebut merupakan kelipatan $n$ — yaitu, jika terdapat suatu bilangan bulat $k$ sedemikian sehingga $a-b=kn$. Kekongruenan modulo $n$ merupakan sebuah relasi kekongruenan, yang berarti bahwa kekongruenan merupakan relasi ekuivalensi yang cocok dengan operasi penambahan, pengurangan, dan perkalian. Kekongruenan modulo $n$ dinotasikan sebagai

$$a\equiv b{\pmod {n}}.$$

Simbol tanda kurung tersebut menunjukkan bahwa ${\pmod {n}}$ berlaku untuk kedua ruas persamaan, tidak hanya untuk ruas kanan (yang dalam kasus ini, $b$). Notasi ini berbeda dengan notasi $b{\bmod {n}}$ (tanpa tanda kurung), yang merujuk kepada sisa dari bilangan $b$ ketika dibagi dengan $n$, yang dikenal sebagai operasi modulus. Dengan kata lain, $b{\bmod {n}}$ adalah suatu bilangan bulat tunggal $s$ sedemikian sehingga $0\leq s<n$ dan memenuhi $s\equiv b{\pmod {n}}$.

Relasi kekongruenan $a$ dengan $b$ dapat ditulis ulang sebagai $$a=kn+b$$ yang secara eksplisit menunjukkan hubungan antara kekongruenan dengan pembagian bersisa. Akan tetapi, nilai $b$ disini tidak harus berupa sisa pembagian $a$ oleh $n$. Justru, $a\equiv b{\pmod {n}}$ berarti bahwa $a$ dan $b$ memiliki sisa yang sama ketika dibagi dengan $n$, yaitu $${\begin{aligned}a&=pn+s\\b&=qn+s\end{aligned}}$$ dengan $0\leq s<n$ adalah sisa pembagian keduanya. Jika ekspresi pertama dikurang dengan ekspresi kedua, maka hubungan sebelumnya (yaitu $a-b=kn$) dapat diperoleh dengan memilih $k=p-q$.

Oleh karena konsep kekongruenan modulo $n$ didefinisikan melalui keterbagian oleh $n$ dan karena $-1$ merupakan unit dalam gelanggang bilangan bulat, suatu bilangan habis dibagi oleh $-n$ jika bilangan tersebut habis dibagi oleh $n$. Hal ini berarti bahwa setiap bilangan bulat tak nol $n$ dapat dijadikan sebagai modulus.

Contoh

Dalam modulus 12, maka $$38\equiv 14{\pmod {12}}$$ sebab selisih dari 38 dan 14 ialah $38-14=24=2\times 12$, yang merupakan kelipatan 12. Hal ini setara dengan mengatakan bahwa 38 dan 14 memiliki sisa yang sama (yakni 2) ketika dibagi dengan 12.

Definisi kekongruenan juga berlaku untuk nilai negatif. Misalnya: $${\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-1&\equiv -16{\pmod {5}}.\end{aligned}}$$

Sifat kekongruenan bilangan bulat

Sifat dasar

Relasi kekongruenan memenuhi semua ketentuan dari relasi ekuivalensi, yaitu:

• Sifat refleksif: $a\equiv a{\pmod {n}}$
• Sifat simetris: $a\equiv b{\pmod {n}}$ jika dan hanya jika $b\equiv a{\pmod {n}}$
• Sifat transitif: Jika $a\equiv b{\pmod {n}}$ dan $b\equiv c{\pmod {n}}$, maka $a\equiv c{\pmod {n}}$

Jika $a\equiv b{\pmod {n}}$ dan $c\equiv d{\pmod {n}}$, maka:

• $a+k\equiv b+k{\pmod {n}}$
• $ak\equiv bk{\pmod {n}}$
• $a+c\equiv b+d{\pmod {n}}$
• $a-c\equiv b-d{\pmod {n}}$
• $ac\equiv bd{\pmod {n}}$
• $a^{k}\equiv b^{k}{\pmod {n}}$ untuk sembarang bilangan bulat nonnegatif $k$
• $p(a)\equiv p(b){\pmod {n}}$ untuk setiap polinomial $p(x)$ dengan koefisien bilangan bulat

Jika $a\equiv b{\pmod {n}}$, maka belum tentu berlaku $k^{a}\equiv k^{b}{\pmod {n}}$. Kekongruenan tersebut akan berlaku jika $k$ relatif prima dengan $n$ dan $a\equiv b{\pmod {\varphi (n)}}$, dengan $\varphi$ adalah fungsi phi Euler.

Jika $a\equiv b{\pmod {mn}}$, maka $a\equiv b{\pmod {m}}$ dan $a\equiv b{\pmod {n}}$.

Untuk operasi pencoretan (pembatalan), maka berlaku sifat-sifat berikut:

• Jika $a+k\equiv b+k{\pmod {n}}$, dengan $k$ adalah sembarang bilangan bulat, maka $a\equiv b{\pmod {n}}$.
• Jika $ak\equiv bk{\pmod {n}}$ dan $k$ relatif prima dengan $n$, maka $a\equiv b{\pmod {n}}$
• Jika $ak\equiv bk{\pmod {kn}}$ dan $k\neq 0$, maka $a\equiv b{\pmod {n}}$

Sifat terakhir dapat digunakan untuk mengubah kekongruenan menjadi pembagian. Jika $b$ habis membagi $a$, maka ${\tfrac {a}{b}}{\bmod {n}}={\tfrac {a{\bmod {bn}}}{b}}$.

Invers perkalian

Invers perkalian modular didefinisikan melalui sifat-sifat berikut:

• Kewujudan: Terdapat suatu bilangan bulat $a^{-1}$ sedemikian sehingga $a\cdot a^{-1}\equiv 1{\pmod {n}}$ jika dan hanya jika $a$ relatif prima dengan modulus $n$. Bilangan bulat $a^{-1}$ disebut sebagai invers perkalian modular dari $a$ dalam modulo $n$.
• Jika $a\equiv b$ dan $a^{-1}$ ada, maka berlaku $a^{-1}\equiv b^{-1}{\pmod {n}}$. Pada kasus $a=b$, hal ini dapat digunakan untuk menunjukkan ketunggalan invers perkalian modulo.
• Jika $ax\equiv b{\pmod {n}}$ dan $a$ relatif prima dengan $n$, maka penyelesaian dari kekongruenan linear tersebut ialah $x\equiv a^{-1}b{\pmod {n}}$

Nilai $a^{-1}$ dalam modulo $n$ dapat ditemukan dengan mencari bilangan bulat $x$ dan $y$ yang memenuhi persamaan Bézout $ax+ny=1$, misalny dengan menggunakan algoritma Euklides diperluas.

Jika $p$ merupakan bilangan prima, maka setiap nilai $a\in \left\{1,\,2,\,3,\,\ldots ,\,p-1\right\}$ akan relatif prima dengan $p$. Akibatnya, setiap nilai $a$ yang tidak kongruen dengan nol dalam modulo $p$ akan memiliki invers perkalian modular.

Sifat-sifat lanjutan

Berikut adalah beberapa sifat-sifat lanjutan mengenai relasi kekongruenan:

• Teorema kecil Fermat: Jika $p$ merupakan bilangan prima yang tidak habis membagi $a$, maka $a^{p-1}\equiv 1{\pmod {p}}$.
• Teorema Euler: Jika $a$ relatif prima dengan $n$, maka $a^{\varphi (n)}\equiv 1{\pmod {n}}$, dengan $\varphi$ menyatakan fungsi phi Euler.
• Akibat sederhana dari teorema kecil Fermat ialah jika $p$ merupakan bilangan prima, maka $a^{-1}\equiv a^{p-2}{\pmod {p}}$ merupakan invers perkalian modular dari $a$ dalam modulo $p$, dengan $0<a<p$.
  • Secara umum, maka berdasarkan teorema Euler, jika $a$ relatif prima dengan $n$, maka $a^{-1}\equiv a^{\varphi (n)-1}{\pmod {n}}$.
• Akibat sederhana lainnya dari teorema Euler ialah jika $k$ relatif prima dengan $n$ dan $a\equiv b{\pmod {\varphi (n)}}$, dengan $\varphi$ menyatakan fungsi phi Euler, maka $k^{a}\equiv k^{b}{\pmod {n}}$.
• Teorema Wilson: $p$ merupakan bilangan prima jika dan hanyaa jika $(p-1)!\equiv -1{\pmod {p}}$.
• Teorema sisa Tiongkok: Jika $m$ relatif prima dengan $n$, maka untuk setiap bilangan bulat $a$ dan $b$, terdapat suatu suatu bilangan bulat $x$ sedemikian sehingga $x\equiv a{\pmod {m}}$ dan $x\equiv b{\pmod {n}}$. Lebih lanjut, $$x\equiv an(n^{-1})_{m}+bm(m^{-1})_{n}$$ dengan $(n^{-1})_{m}$ menyatakan invers perkalian modular dari $n$ pada modulo $m$ dan $(m^{-1})_{n}$ menyatakan invers perkalian modular dari $m$ pada modulo $n$.
• Teorema Lagrange: Jika $p$ merupakan bilangan prima dan $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n}x^{n}$ merupakan polinomial dengan koefisien bilangan bulat sedemikian sehingga $p$ tidak habis membagi $a_{n}$, maka kekongruenan $f(x)\equiv 0{\pmod {p}}$ memiliki paling banyak $n$ penyelesaian yang tidak saling kongruen.
• Akar primitif modulo n: Bilangan $g$ disebut sebagai akar primitif modulo $n$ jika untuk setiap bilangan bulat $a$ yang relatif prima dengan $n$, maka terdapat suatu bilangan bulat $k$ sedemikian sehingga $g^{k}\equiv a{\pmod {n}}$. Akar primitif modulo $n$ terjamin ada jika dan hanya jika nilai $n$ sama dengan 1, 2, 4, $p^{k}$, atau $2p^{k}$, dengan $p$ adalah bilangan prima ganjil dan $k$ adalah bilangan asli. Jika terdapat akar primitif modulo $n$, maka banyaknya akar primitif ialah $\varphi (\varphi (n))$, dengan $\varphi$ menyatakan fungsi phi Euler.
• Residu kuadratik: Bilangan bulat $a$ dikatakan sebagai residu kuadratik modulo $n$, jika terdapat suatu bilangan bulat $k$ yang memenuhi kekongruenan $k^{2}\equiv a{\pmod {n}}$. Kriteria Euler menunjukkan bahwa jika $p$ merupakan bilangan prima ganjil dan $a$ bukan kelipatan $p$, maka $a$ merupakan residu kuadratik modulo $p$ jika dan hanya jika $$a^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}.$$

Kelas-kelas kekongruenan

Relasi kekongruenan merupakan relasi ekuivalensi. Kelas ekuivalen modulo $n$ dari bilangan bulat $a$ ialah himpunan semua bilangan bulat dengan bentuk umum $a+kn$, dengan $k$ adalah sembarang bilangan bulat. Dengan menggunakan notasi ungkapan himpunan, maka kelas ekuivalen modulo $n$ dari bilangan bulat $a$ ialah $$\left\{a+kn\mid k\in \mathbb {Z} \right\}=\left\{\ldots ,\,a-2n,\,a-n,\,a,\,a+n,\,a+2n,\,\ldots \right\}$$ Himpunan ini disebut sebagai kelas kekongruenan atau kelas residu dari $a$ modulo $n$; dan dinotasikan sebagai $(a{\bmod {n}})$, ${\overline {a}}_{n}$, $\left[a\right]_{n}$, atau cukup ${\overline {a}}$ atau $\left[a\right]$ jika nilai modulus $n$ nya telah diketahui berdasarkan konteks.

Setiap kelas residu modulo $n$ memuat tepat satu dari $\left|n\right|$ bilangan bulat pada himpunan $\left\{0,\,1,\,2,\,\ldots ,\,\left|n\right|-1\right\}$. Akibatnya, $\left|n\right|$ bilangan bulat ini merupakan perwakilan dari masing-masing kelas residu.

Sistem residu

Setiap kelas residu modulo $n$ dapat diwakili oleh salah satu anggotanya, meskipun sering kali perwakilan dari setiap kelas residu merupakan bilangan bulat nonnegatif terkecil pada kelas tersebut (sebab bilangan tersebut merupakan nilai yang dihasilkan melalui pembagian bersisa). Setiap dua anggota dari kelas residu modulo $n$ yang berbeda tidak akan kongruen dalam modulo $n$. Selain itu, setiap bilangan bulat berada pada satu dan hanya satu kelas residu modulo $n$.

Himpunan bilangan bulat $\left\{0,\,1,\,2,\,\ldots ,\,n-1\right\}$ disebut sebagai sistem residu terkecil modulo n. Setiap himpunan $n$ bilangan bulat yang tidak memiliki pasangan bilangan yang saling kongruen modulo $n$ disebut sebagai sistem residu lengkap modulo n.

Sistem residu terkecil merupakan sistem residu lengkap, dan sistem residu lengkap pada dasarnya adalah suatu himpunan yang berisi tepat satu perwakilan dari setiap kelas residu modulo $n$. Sebagai contoh, sistem residu terkecil modulo 4 ialah $\left\{0,\,1,\,2,\,3\right\}$. Beberapa sistem residu lengkap modulo 4 lainnya meliputi:

• $\left\{1,\,2,\,3,\,4\right\}$
• $\left\{13,\,14,\,15,\,16\right\}$
• $\left\{-2,\,-1,\,0,\,1\right\}$
• $\left\{-13,\,4,\,17,\,18\right\}$
• $\left\{-5,\,0,\,6,\,21\right\}$
• $\left\{27,\,32,\,37,\,-42\right\}$

Beberapa himpunan yang bukan merupakan sistem residu lengkap modulo 4 adalah:

• $\left\{-5,\,0,\,6,\,22\right\}$, sebab 6 kongruen dengan 22 dalam modulo 4.
• $\left\{5,\,15\right\}$, sebab sistem residu lengkap modulo 4 harus memiliki tepat 4 kelas residu yang tidak kongruen.

Sistem residu tereduksi

Artikel utama: Sistem residu tereduksi

Diberikan Fungsi phi Euler $\varphi$, setiap himpunan $\varphi (n)$ bilangan bulat yang relatif prima dengan $n$ dan tidak memiliki pasangan bilangan yang saling kongruen dalam modulo $n$ disebut sebagai sistem residu tereduksi modulo n. Sebagai contoh, himpunan $\left\{5,\,15\right\}$ pada bagian sebelumnya adalah sistem residu tereduksi modulo 4.

Sistem peliput

Artikel utama: Sistem peliput

Sistem peliput menyatakan jenis sistem residu lain yang mungkin saja memuat kelas-kelas residu dengan modulo yang beragam.

Objek dengan aritmetika modular

Bilangan bulat modulo n

Dalam konteks paragraf ini, modulus $n$ hampir selalu diasumsikan bernilai positif.

Himpunan semua kelas-kelas kekongruenan modulo $n$ merupakan sebuah gelanggang, yang disebut sebagai gelanggang bilangan bulat modulo n dan ditulis sebagai ${\textstyle \mathbb {Z} /n\mathbb {Z} }$, $\mathbb {Z} /n$, atau $\mathbb {Z} _{n}$. Akan tetapi, notasi $\mathbb {Z} _{n}$ tidak disarankan sebab bisa disalahartikan sebagai himpunan bilangan bulat p-adik. Gelanggang $\mathbb {Z} /n\mathbb {Z}$ merupakan objek fundamental untuk berbagai cabang matematika (lihat § Aplikasi di bawah).

Untuk bilangan asli $n$, gelanggang ini didefinisikan sebagai:

$$\mathbb {Z} /n\mathbb {Z} =\left\{[k]_{n}\mid k\in \mathbb {Z} \right\}=\left\{[0]_{n},\,[1]_{n},\,[2]_{n},\,\ldots ,\,[n-1]_{n}\right\}.$$

Jika $n=1$, maka $\mathbb {Z} /n\mathbb {Z}$ merupakan gelanggang nol. Jika $n=0$, maka $\mathbb {Z} /n\mathbb {Z}$ bukanlah himpunan kosong, melainkan sebuah himpunan yang isomorfik dengan $\mathbb {Z}$, sebab $[k]_{0}=\left\{k\right\}$.

Operasi penjumlahan, pengurangan, dan perkalian pada $\mathbb {Z} /n\mathbb {Z}$ didefinisikan sebagai:

• $[a]_{n}+[b]_{n}=[a+b]_{n}$
• $[a]_{n}-[b]_{n}=[a-b]_{n}$
• $[a]_{n}\;[b]_{n}=[ab]_{n}.$

Berdasarkan sifat-sifat dasar dari kekongruenan serta tiga definisi operasi pada $\mathbb {Z} /n\mathbb {Z}$, maka $\mathbb {Z} /n\mathbb {Z}$ adalah gelanggang komutatif. Misalnya, dalam gelanggang $\mathbb {Z} /24\mathbb {Z}$, maka berlaku $$[12]_{24}+[21]_{24}=[33]_{24}=[9]_{24}$$ seperti dalam aritmetika untuk sistem 24 jam.

Notasi $\mathbb {Z} /n\mathbb {Z}$ terkadang digunakan, sebab gelanggang ini merupakan gelanggang hasil bagi dari $\mathbb {Z}$ oleh ideal $n\mathbb {Z}$, yaitu himpunan yang memuat semua kelipatan $n$ — atau dengan kata lain, semua bilangan dengan bentuk umum $kn$, dengan $k\in \mathbb {Z}$.

Himpunan $\mathbb {Z} /n\mathbb {Z}$ merupakan grup siklik terhadap operasi penjumlahan. Semua grup siklik hingga isomorfik dengan $\mathbb {Z} /n\mathbb {Z}$, untuk suatu $n\in \mathbb {N}$.

Jika $n>1$, maka $\left(\mathbb {Z} /n\mathbb {Z} ,\,\times \right)$ menyatakan grup perkalian bilangan bulat modulo n yang memiliki invers perkalian. Himpunan tersebut berisi kelas-kelas kekongruenan $[a]_{n}$ yang relatif prima dengan $n$. Semua elemen pada himpunan tersebut memiliki invers perkalian modulo $n$, sehingga himpunan tersebut membentuk grup Abelian terhadap operasi perkalian. Orde dari $\left(\mathbb {Z} /n\mathbb {Z} ,\,\times \right)$ ialah $\varphi (n)$, dengan $\varphi$ menyatakan fungsi phi Euler.

Polinomial

Artikel utama: polinomial siklotomik

Konstruksi dengan penggaris dan jangka dari segi-17 beraturan dengan menggunakan teknik aritmetika modular.

Gauss menyadari bahwa aritmetika modular juga dapat diterapkan pada himpunan polinomial dengan koefisien bilangan rasional, 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 $x^{n}-1$ dan menemukan faktor-faktor primitifnya, yang disebut dengan polinomial siklotomik. Hal ini digunakan untuk menemukan konstruksi penggaris dan jangka dari heptadekagon, sebuah segi-17 beraturan. 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, tetapi prinsipnya didapatkan dari aritmetika tingkat lanjut".

Bilangan aljabar

Artikel utama: Bilangan bulat Gauss

Pada kasus polinomial dengan koefisien bilangan bulat, sifat pembagian hanya berlaku untuk polinomial monik. Bagian ini membahas modulus berupa polinomial $X^{2}+1$, dengan struktur modular yang didapatkan masih bagian dari gelanggangnya. Gelanggang ini berisi himpunan bilangan dalam bentuk $\alpha +i\beta$, dengan $\alpha$ dan $\beta$ berupa bilangan bulat dan $i$ berupa unit bilangan imajiner, yang berkorespodensi dengan monomial $X$. Himpunan tersebut dikenal sebagai bilangan

Perkembangan teoretis

Dalam matematika, umum dijumpai sebuah konsep matematika yang dikembangkan dalam sebuah bidang, namun 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.

Struktur hasil bagi

Artikel utama: relasi ekuivalensi

Dalam matematika modern, aritmetika modular diformalkan dengan menggunakan konsep gelanggang Euklides. Konsep relasi ekuivalensi memungkinkan aritmetika modular diterapkan ke banyak struktur aljabar. Sebagai contoh, hasil bagi sebuah grup dengan sebuah subgrup normal, dengan menggunakan teorema Jordan–Hölder, adalah alat dasar untuk mengklasifikasikan grup hingga. Grup hasil bagi juga digunakan dalam topologi aljabar untuk mengelompokkan lipatan.

Aplikasi

Dalam matematika teoretis, aritmetika 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 visual dan seni musikal.

Aplikasi yang sangat praktis adalah menghitung checksum dalam pengenal bilangan deret. Misalnya, Nomor Buku Standar Internasional (ISBN) menggunakan aritmetika 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 aritmetika 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, aritmetika modular secara langsung mendukung sistem kunci publik seperti RSA dan 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, aritmetika 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 aritmetika 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, aritmetika 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.

Dalam ilmu komputer, aritmetika 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.

Lihat pula

• Gelanggang Boolean
• Penyangga melingkar
• Pembagian
• Medan hingga
• Simbol Legendre
• Eksponen modular
• Modulo (matematika)
• Grup perkalian bilangan bulat modulo n
• Periode Pisano (deret Fibonacci modulo n)
• Akar primitif modulo n
• Timbal balik kuadratik
• Residu kuadratik
• Rekonstruksi rasional (matematika)
• Sistem residu tereduksi
• Aritmetika bilangan deret (kasus khusus aritmetika modular)
• Aljabar Boolean dua elemen
• Topik yang berkaitan dengan teori grup di balik aritmetika modular:
  • Grup siklik
  • Grup perkalian bilangan bulat modulo n
• Teorema penting lainnya yang berkaitan dengan aritmetika modular:
  • Teorema Carmichael
  • Teorema sisa Tiongkok
  • Teorema Euler
  • Teorema kecil Fermat (kasus khusus dari teorema Euler)
  • Teorema Lagrange
  • Lemma Thue

Referensi

• (Inggris) John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
• (Inggris) Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
• (Inggris) Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
• (Inggris) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
• (Inggris) Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3.
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (dalam bahasa Inggris) (Edisi 2nd). Lexington: D. C. Heath and Company. LCCN 77171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory (dalam bahasa Inggris). Englewood Cliffs: Prentice Hall. LCCN 71081766.
• Sengadir, T. (2009). Discrete Mathematics and Combinatorics (dalam bahasa Inggris). Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Pranala luar

• Hazewinkel, Michiel, ed. (2001) [1994], "Congruence", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
• (Inggris) Artikel seni modular ini memberikan wawasan mengenai penerapan aritmetika modular dalam seni.
• (Inggris) Sebuah artikel mengenai aritmetika modular di wiki GIMPS
• (Inggris) Modular Arithmetic and patterns in addition and multiplication tables