Teorema sisa Tiongkok dijelaskan

Sebuah bilangan bersisa 2 bila dibagi 3, bersisa 3 bila dibagi 5, dan bersisa 2 bila dibagi 7. Bilangan berapa itu? Coba bilangan satu per satu dan setelah beberapa saat Anda sampai di 23, tetapi pertanyaan ini menyimpan sebuah teorema: selama pembagi-pembaginya tidak punya faktor persekutuan, selalu ada tepat satu jawaban di bawah hasil kalinya, dan jawaban itu bisa ditemukan tanpa mencoba apa pun. Teorema ini berumur sekitar 1.500 tahun dan masih bekerja di kalender, aritmetika komputer, dan kriptografi yang melindungi web.

Tiga baris tanda untuk bilangan yang bersisa 2 mod 3, 3 mod 5, dan 2 mod 7, yang bertemu dalam satu kolom di 23
Tiga baris tanda untuk bilangan yang bersisa 2 mod 3, 3 mod 5, dan 2 mod 7, yang bertemu dalam satu kolom di 23

Soal dari Sunzi Suanjing

Sunzi Suanjing, buku aritmetika Tiongkok dari abad ke-3 sampai ke-5, menanyakan sejumlah benda yang bersisa 2 bila dihitung tiga-tiga, 3 bila dihitung lima-lima, dan 2 bila dihitung tujuh-tujuh. Jawabannya 23, dan metodenya masih diajarkan sampai sekarang: ambil 70 untuk setiap benda yang tersisa saat dihitung tiga-tiga, 21 untuk setiap benda yang tersisa saat dihitung lima-lima, dan 15 untuk setiap benda yang tersisa saat dihitung tujuh-tujuh, jumlahkan, lalu kurangi 105 sebanyak mungkin. 2 × 70 + 3 × 21 + 2 × 15 = 233, dan 233 − 2 × 105 = 23. Sebuah sajak dari zaman Ming menjaga bilangan 70, 21, 15, dan 105 dalam ingatan selama berabad-abad. Qin Jiushao memberi metode umum pada 1247, soal yang sama muncul di Liber Abaci karya Fibonacci tahun 1202, dan Carl Friedrich Gauss merumuskan teorema itu dalam bentuk modernnya di Disquisitiones Arithmeticae tahun 1801.

Sebuah halaman dari edisi Dinasti Qing Sunzi Suanjing, buku aritmetika Tiongkok abad ke-3 hingga ke-5 yang meminta bilangan yang bersisa 2, 3, dan 2 bila dihitung dengan tiga, lima, dan tujuh.
Sebuah halaman dari edisi Dinasti Qing Sunzi Suanjing, buku aritmetika Tiongkok abad ke-3 hingga ke-5 yang meminta bilangan yang bersisa 2, 3, dan 2 bila dihitung dengan tiga, lima, dan tujuh.
Carl Friedrich Gauss, dalam potret Christian Albrecht Jensen tahun 1840. Ia memperkenalkan notasi kongruensi a ≡ b (mod n) dalam Disquisitiones Arithmeticae tahun 1801.
Carl Friedrich Gauss, dalam potret Christian Albrecht Jensen tahun 1840. Ia memperkenalkan notasi kongruensi a ≡ b (mod n) dalam Disquisitiones Arithmeticae tahun 1801.

Apa isi teorema ini

Ambil modulus n₁, n₂, …, nₖ yang tidak ada dua di antaranya punya faktor persekutuan, dan sisa a₁, a₂, …, aₖ berapa saja. Maka ada tepat satu bilangan bulat x dari 0 sampai N − 1, dengan N = n₁ × n₂ × … × nₖ, yang bersisa aᵢ bila dibagi nᵢ, untuk setiap i. Semua solusi lain berbeda darinya sebesar kelipatan N. Dalam notasi aritmetika modular: sistem x ≡ aᵢ (mod nᵢ) punya solusi, dan solusinya tunggal mod N. Dengan kata lain, sebuah bilangan dari 0 sampai N − 1 dan daftar sisanya membawa informasi yang persis sama: 3 × 5 × 7 = 105 bilangan dan 3 × 5 × 7 = 105 kemungkinan daftar sisa, masing-masing dipakai satu kali.

Membangun solusi

Bilangan 70, 21, dan 15 bukan sihir. Masing-masing bersisa 1 bila dibagi modulusnya sendiri dan bersisa 0 bila dibagi modulus lainnya: 70 = 2 × 35 adalah kelipatan 5 dan 7 serta bersisa 1 bila dibagi 3. Secara umum, ambil Nᵢ = N / nᵢ, kelipatan setiap modulus kecuali nᵢ, lalu kalikan dengan yᵢ, invers Nᵢ mod nᵢ. Invers itu ada karena Nᵢ dan nᵢ tidak punya faktor persekutuan, dan algoritma Euklides yang diperluas menemukannya: algoritma ini menjalankan pembagian Euklides untuk faktor persekutuan terbesar lalu menghitung mundur sampai identitas Bézout 1 = s × nᵢ + t × Nᵢ, sehingga t adalah inversnya. Maka x = a₁N₁y₁ + a₂N₂y₂ + …, direduksi mod N, cocok dengan setiap persamaan, karena setiap suku cocok dengan persamaannya sendiri dan lenyap di semua persamaan lain.

Satu persamaan demi satu

Ada cara kedua yang tidak memerlukan hasil kali semua modulus. Setiap solusi x ≡ 2 (mod 3) berbentuk x = 2 + 3t. Masukkan ke persamaan berikutnya: 2 + 3t ≡ 3 (mod 5), jadi 3t ≡ 1 (mod 5), dan mengalikan dengan 2, invers 3 mod 5, menghasilkan t ≡ 2 (mod 5). Maka x = 2 + 3 × 2 = 8, dan dua persamaan pertama bersama-sama menyatakan x ≡ 8 (mod 15). Ulangi dengan persamaan ketiga: 8 + 15t ≡ 2 (mod 7) menghasilkan t ≡ 1, jadi x ≡ 23 (mod 105). Substitusi ini menjaga bilangan tetap kecil, merupakan cara komputer biasanya menyelesaikan sistem seperti ini, dan tetap berhasil bila modulusnya punya faktor persekutuan.

Modulus dengan faktor persekutuan

Jika dua modulus punya faktor persekutuan, persamaannya saling tumpang tindih: x ≡ 1 (mod 4) sudah menyatakan bahwa x ganjil, dan x ≡ 4 (mod 6) menyatakan bahwa x genap, jadi tidak ada x yang memenuhi keduanya. Secara umum, x ≡ a (mod m) dan x ≡ b (mod n) bisa berlaku bersamaan tepat bila a dan b bersisa sama bila dibagi g = gcd(m, n), yaitu bila g membagi a − b. Maka solusinya tunggal mod lcm(m, n) = m × n / g, bukan mod m × n. Teka-teki lama tentang keranjang telur, yang menyisakan 1 bila telurnya diambil 2, 3, 4, 5, atau 6 sekaligus dan tidak menyisakan apa pun bila diambil 7 sekaligus, punya jawaban 301, yang berulang setiap 420 = lcm(2, 3, 4, 5, 6, 7). Sebuah sistem punya solusi tepat bila setiap pasang persamaannya cocok, jadi sistem yang mustahil selalu memuat pasangan yang bertentangan.

Kalender, komputer, dan RSA

Pada 1583 Joseph Scaliger menggabungkan tiga siklus kalender, siklus matahari 28 tahun, siklus bulan 19 tahun, dan indiksi 15 tahun, menjadi periode Julian 28 × 19 × 15 = 7.980 tahun. Menurut teorema ini, setiap tahun punya kombinasi tiga nomor siklus yang khas, dan periodenya dimulai pada 4713 SM, tahun terakhir ketika ketiganya bernilai 1; para astronom masih menghitung hari Julian dari sana. Komputer memakai teorema ini untuk menghitung bilangan raksasa sebagai daftar sisa kecil, yang bisa dijumlahkan dan dikalikan secara terpisah dan paralel, lalu digabungkan di akhir. Dekripsi RSA bekerja dengan cara yang sama: c^d mod n dengan n = p × q dihitung sebagai dua perpangkatan mod p dan mod q yang digabungkan dengan teorema, sekitar empat kali lebih cepat daripada satu perpangkatan mod n. Skema berbagi rahasia, seperti skema Mignotte serta Asmuth dan Bloom, menyembunyikan rahasia dalam sisa-sisa sehingga hanya cukup banyak sisa bersama-sama yang dapat mengungkapnya.

Ron Rivest, Adi Shamir, dan Len Adleman (dari kiri ke kanan)
Ron Rivest, Adi Shamir, dan Len Adleman (dari kiri ke kanan)

Coba sendiri

Buka kalkulator untuk mengetik sistem kongruensi apa saja, hingga 20 persamaan dan bilangan paling banyak 200 digit, atau pilih salah satu contoh soal: soal Sunzi, keranjang telur, periode Julian, jadwal dua bus, dekripsi RSA, dan sistem tanpa solusi. Penyelesaiannya ditulis dengan bilangan Anda, dengan konstruksi atau substitusi, dengan algoritma Euklides yang diperluas untuk setiap invers. Gambar menandai bilangan yang memenuhi setiap persamaan, sehingga Anda melihat satu-satunya kolom tempat semuanya bertemu, atau menata sisa dua persamaan dalam tabel tempat setiap bilangan punya selnya sendiri.

Pertanyaan yang sering diajukan

Apakah solusi sistem kongruensi tunggal?

Hanya sampai kelipatan modulusnya. Jika x = 23 menyelesaikan soal Sunzi, maka 23 + 105 = 128, 233, dan −82 juga, karena menambah 105 tidak mengubah sisa mana pun. Teorema ini menyatakan ada tepat satu solusi dari 0 sampai 104; untuk modulus yang punya faktor persekutuan, tepat satu di bawah kelipatan persekutuan terkecilnya.

Mengapa modulusnya harus saling prima?

Untuk konstruksi, karena Nᵢ harus punya invers mod nᵢ, dan invers itu hanya ada bila keduanya tidak punya faktor persekutuan. Untuk teoremanya sendiri, karena faktor persekutuan membuat sebagian persamaan tumpang tindih: maka sistem tidak punya solusi atau punya lebih sedikit solusi yang berbeda, dan solusinya berulang setiap kelipatan persekutuan terkecil, bukan setiap hasil kali.

Bagaimana mencari invers modular dengan tangan?

Dengan algoritma Euklides yang diperluas. Untuk invers 15 mod 7: 15 = 2 × 7 + 1, jadi 1 = 15 − 2 × 7, dan 15 × 1 ≡ 1 (mod 7): inversnya 1. Untuk 35 mod 3: 35 = 11 × 3 + 2 dan 3 = 1 × 2 + 1, jadi 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, dan invers 35 mod 3 adalah −1 ≡ 2. Untuk modulus kecil, Anda juga bisa mencoba 1, 2, 3, … sampai hasil kalinya bersisa 1.

Apa hubungan teorema ini dengan jam?

Sisa mod n adalah posisi pada jam dengan n jam. Dua jam dengan 3 dan 5 jam yang mulai bersamaan dan maju satu jam setiap kali menunjukkan masing-masing dari 15 pasangan posisi satu kali sebelum kembali ke awal, karena 3 dan 5 tidak punya faktor persekutuan. Jam dengan 4 dan 6 jam kembali setelah 12 langkah dan hanya menunjukkan 12 dari 24 pasangan: posisi ganjil dan genap tidak pernah muncul bersamaan.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka kalkulator teorema sisa Tiongkok