Aritmetika modular dijelaskan
Semua orang sudah melakukan aritmetika modular: 10 jam setelah pukul 8 adalah pukul 6, dan hari setelah Minggu adalah Senin. Berhitung yang mulai lagi dari 0 setelah n langkah ternyata memiliki aritmetikanya sendiri yang lengkap, dengan aturan, kejutan, dan tempat sentral dalam teori bilangan serta dalam kriptografi yang melindungi internet.
Sisa dan kongruensi
Bagi a dengan n dan simpan hanya sisanya: itulah a mod n, sebuah bilangan dari 0 hingga n − 1. 26 mod 7 = 5, karena 26 = 3 × 7 + 5. Bilangan dengan sisa yang sama berperilaku sama mod n, sehingga kita menyebutnya kongruen: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss memperkenalkan notasi ini dalam Disquisitiones Arithmeticae tahun 1801, dan notasi itu menjadikan pengamatan lama Fermat dan Euler sebuah aritmetika tersendiri. Pada jam dengan n posisi, setiap bilangan bulat mendarat di sisanya; putaran penuhnya dilupakan.
Menjumlahkan, mengurangkan, dan mengalikan
Ketiga operasi biasa bekerja seperti biasa, dan Anda boleh mereduksi mod n kapan pun Anda mau: sisa dari suatu jumlah adalah sisa dari jumlah sisa-sisanya, dan hal yang sama berlaku untuk selisih dan hasil kali. Untuk mencari digit terakhir 37 × 48, kalikan hanya digit terakhirnya: 7 × 8 = 56, jadi hasilnya berakhiran 6. Inilah yang membuat aritmetika modular begitu berguna bagi komputer: sebesar apa pun bilangannya, nilai perantaranya tidak pernah melebihi n².
Pembagian memerlukan invers
Pembagian adalah pengecualian. 2 × 3 ≡ 2 × 8 (mod 10), karena keduanya 6 mod 10, tetapi 3 dan 8 berbeda, jadi Anda tidak bisa begitu saja mencoret angka 2. Membagi dengan a berarti mengalikan dengan inversnya, bilangan x dengan a × x ≡ 1, dan invers itu ada tepat ketika a dan n tidak memiliki faktor persekutuan. Algoritma Euklides yang diperluas menemukannya: algoritma ini menjalankan langkah-langkah pembagian Euklides untuk faktor persekutuan terbesar dan mencatat sebuah pengali di setiap langkah, sehingga ketika sisanya mencapai 1, pengali itu adalah inversnya. Jika n prima, setiap bilangan kecuali 0 memiliki invers, dan pembagian selalu bisa dilakukan.
Perpangkatan, Fermat, dan Euler
Perpangkatan berulang. Ambil pangkat-pangkat 3 mod 7: 3, 2, 6, 4, 5, 1, lalu 3 lagi. Panjang siklus itu adalah orde 3. Pada tahun 1640 Pierre de Fermat memperhatikan bahwa untuk bilangan prima p, a^(p − 1) ≡ 1 (mod p) setiap kali p tidak membagi a, sehingga setiap orde membagi p − 1. Leonhard Euler membuktikannya dan memperluasnya ke sembarang n, dengan p − 1 diganti banyaknya nilai yang koprima dengan n. Pangkat yang sangat besar dihitung dengan pengkuadratan berulang: a, a², a⁴, a⁸ … masing-masing kuadrat dari yang sebelumnya, direduksi mod n, lalu dikalikan sesuai digit biner eksponennya.
Digit pemeriksa dan kalender
Aritmetika modular menangkap kesalahan. Digit terakhir ISBN-10 dipilih sedemikian rupa sehingga jumlah berbobot dari kesepuluh digitnya merupakan kelipatan 11, sehingga setiap satu digit yang salah dan setiap pertukaran dua digit yang bersebelahan terdeteksi. Nomor kartu bank menggunakan pemeriksaan Luhn mod 10, dan IBAN pemeriksaan mod 97. Kalender berjalan mod 7: hari dari tanggal mana pun dapat dihitung dengan beberapa sisa pembagian, dan begitulah cara kerja kalender abadi dan aturan doomsday.
Kriptografi
Kriptografi modern dibangun di atas perpangkatan modular yang mudah dihitung dan sulit dibalik. Dalam pertukaran kunci Diffie–Hellman tahun 1976, dua orang menyepakati rahasia bersama melalui saluran terbuka dengan saling bertukar pangkat mod sebuah bilangan prima besar. RSA, yang diterbitkan pada tahun 1977 oleh Rivest, Shamir, dan Adleman, mengenkripsi pesan m sebagai m^e mod n, dengan n hasil kali dua bilangan prima besar, dan mendekripsi dengan eksponen kedua d yang hanya dapat dihitung oleh orang yang mengetahui kedua bilangan prima itu. Dalam contoh buku teks, n = 3233 = 61 × 53, e = 17, dan d = 413: 65 menjadi 2790, dan 2790 kembali menjadi 65.
Jelajahi sendiri
Buka jam modular untuk menghitung a mod n, jumlah, selisih, hasil kali, perpangkatan, invers, dan hasil bagi mod n, untuk bilangan hingga 30 digit. Setiap jawaban disertai langkah-langkahnya: pembagian bersisa, pangkat-pangkat dari pengkuadratan berulang, atau tabel algoritma Euklides yang diperluas. Jam menggambarkan bagaimana jawaban dicapai, dari spiral penjumlahan hingga siklus perpangkatan, dan untuk n kecil tabel operasi menampilkan semua jawaban sekaligus.
Pertanyaan yang sering diajukan
Apa arti simbol ≡?
a ≡ b (mod n) menyatakan bahwa a dan b memiliki sisa yang sama ketika dibagi n, atau dengan kata lain n membagi a − b. 38 ≡ 2 (mod 12), karena 38 − 2 = 36 adalah kelipatan 12.
Apakah mod sama dengan operator % dalam pemrograman?
Untuk bilangan positif, ya. Untuk bilangan negatif, banyak bahasa seperti C, Java, dan JavaScript mengembalikan sisa negatif: di sana −7 % 3 bernilai −1, sedangkan −7 mod 3 = 2. Operator % pada Python mengikuti konvensi matematika untuk n positif.
Apa orde suatu bilangan mod n?
k > 0 terkecil dengan a^k ≡ 1 (mod n). Orde hanya ada jika a dan n tidak memiliki faktor persekutuan. Orde 2 mod 7 adalah 3, karena 2³ = 8 ≡ 1, dan orde 3 mod 7 adalah 6, sehingga pangkat-pangkat 3 melewati setiap sisa yang bukan nol: 3 adalah akar primitif mod 7.
Siapa yang menemukan aritmetika modular?
Sisa pembagian sudah digunakan jauh sebelumnya, misalnya dalam teorema sisa Tiongkok dari abad ke-3 hingga ke-5, serta oleh Fermat dan Euler. Gauss menjadikannya aritmetika yang sistematis, dengan notasi kongruensi, pada tahun 1801.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Buka jam modular