Kalkulator teorema sisa Tiongkok
Hitung setumpuk benda tiga-tiga dan sisa 2, lima-lima sisa 3, tujuh-tujuh sisa 2: ada 23 benda, atau 128, atau 233, satu jawaban setiap 105. Itulah soal dari Sunzi Suanjing yang memberi nama pada teorema sisa Tiongkok. Ketik sistem kongruensi x ≡ a (mod n) apa saja, dengan persamaan sebanyak dan bilangan sebesar yang Anda mau, lalu lihat jawabannya, penyelesaian dengan bilangan Anda, dan gambar yang menunjukkan mengapa cara ini berhasil. Bila persamaan-persamaan itu tidak bisa berlaku semuanya, kalkulator menyebut dua persamaan yang bertentangan dan menunjukkan alasannya. Ketik persamaan x ≡ a (mod n), satu per baris: a adalah sisa dan n modulus. Tambahkan baris dengan Tambah persamaan, atau dengan Enter di modulus terakhir, dan hapus dengan ×. Bilangan bulat hingga 200 digit bisa dipakai, dan a boleh negatif. Atau pilih contoh soal. Kotak-kotak menunjukkan solusi terkecil dan setiap berapa solusi itu berulang; di bawahnya ada solusi positif pertama dan pemeriksaan setiap persamaan. Gambar menandai bilangan yang memenuhi setiap persamaan, dan kolom yang punya tanda di setiap baris adalah solusinya; tabel sisa menampilkan dua persamaan sekaligus. Penyelesaiannya ditulis dengan bilangan Anda, dengan konstruksi buku pelajaran atau dengan substitusi.
Cara kerjanya
- Ketik persamaan x ≡ a (mod n), satu per baris, atau pilih contoh soal seperti soal Sunzi, keranjang telur, atau periode Julian.
- Baca solusi terkecil, modulus tempat solusi itu berulang, dan solusi positif pertama, masing-masing diperiksa terhadap setiap persamaan.
- Ikuti penyelesaiannya langkah demi langkah, dengan konstruksi atau substitusi, dan alihkan gambar antara garis bilangan dan tabel sisa.
Cara kerja konstruksi
Bila tidak ada dua modulus yang punya faktor persekutuan, solusinya bisa dibangun langsung. Kalikan semua modulus: untuk soal Sunzi, N = 3 × 5 × 7 = 105. Untuk setiap persamaan ambil Nᵢ = N / nᵢ, kelipatan setiap modulus lain: 35, 21, dan 15. Lalu cari invers yᵢ dari Nᵢ mod nᵢ dengan algoritma Euklides yang diperluas: 35 bersisa 2 bila dibagi 3, dan 2 × 2 = 4 ≡ 1 (mod 3), jadi y₁ = 2; 21 dan 15 bersisa 1, jadi inversnya 1. Sekarang x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, dan 233 mod 105 = 23. Setiap suku cocok dengan persamaannya sendiri dan merupakan kelipatan modulus lainnya, jadi jumlahnya cocok dengan semuanya.
Bila modulus punya faktor persekutuan
Sistem yang modulusnya punya faktor persekutuan pun bisa punya solusi. Dua persamaan x ≡ a (mod m) dan x ≡ b (mod n) bisa berlaku bersamaan tepat bila a − b kelipatan gcd(m, n), dan solusinya lalu berulang setiap lcm(m, n), bukan setiap m × n. Dua bus yang berangkat pada menit ke-5 dan ke-11, setiap 12 dan setiap 18 menit, bertemu pada menit ke-29 dan setelah itu setiap 36 menit, karena 11 − 5 = 6 kelipatan gcd(12, 18) = 6. Tetapi x ≡ 1 (mod 4) dan x ≡ 4 (mod 6) tidak pernah bisa berlaku bersamaan: yang pertama membuat x ganjil dan yang kedua membuatnya genap. Seluruh sistem punya solusi tepat bila setiap pasang persamaannya punya solusi, dan dengan cara itulah kalkulator menemukan dua persamaan yang bertentangan.
Pertanyaan yang sering diajukan
Apa isi teorema sisa Tiongkok?
Jika tidak ada dua modulus n₁, n₂, … yang punya faktor persekutuan, maka untuk sisa a₁, a₂, … berapa pun ada tepat satu x dari 0 sampai N − 1 dengan x ≡ aᵢ (mod nᵢ) untuk setiap i, dengan N hasil kali semua modulus. Setiap solusi lain berbeda darinya sebesar kelipatan N: untuk soal Sunzi solusinya 23, 128, 233, dan seterusnya, satu setiap 105.
Mengapa disebut Tiongkok?
Soal tertua yang diketahui dari jenis ini ada di Sunzi Suanjing, buku aritmetika Tiongkok yang ditulis antara abad ke-3 dan ke-5: dihitung tiga-tiga, lima-lima, dan tujuh-tujuh, sejumlah benda bersisa 2, 3, dan 2. Qin Jiushao memberi metode umum untuk soal semacam itu pada 1247, dan Carl Friedrich Gauss merumuskan teorema itu dalam bentuk modernnya pada 1801.
Bagaimana jika modulusnya tidak saling prima?
Maka mungkin tidak ada solusi, dan bila ada, solusinya berulang setiap kelipatan persekutuan terkecil modulus, bukan setiap hasil kalinya. Dua persamaan cocok bila sisanya sama modulo gcd modulus-modulusnya. Teka-teki telur memakai 2, 3, 4, 5, 6, dan 7 yang punya faktor persekutuan, dan tetap punya solusi: 301, yang berulang setiap 420.
Bagaimana RSA memakai teorema sisa Tiongkok?
Mendekripsi pesan RSA berarti menghitung c^d mod n, dengan n = p × q. Lebih cepat menghitung c^d mod p dan c^d mod q secara terpisah, dengan eksponen direduksi mod p − 1 dan q − 1, lalu menggabungkan kedua hasil dengan teorema itu. Dengan bilangan yang panjangnya separuh, setiap perpangkatan hanya memerlukan sekitar seperdelapan pekerjaan, jadi dekripsi sekitar empat kali lebih cepat, dan sebagian besar perangkat lunak RSA melakukannya dengan cara ini.
Seberapa besar bilangannya boleh?
Hingga 20 persamaan, dengan bilangan masing-masing paling banyak 200 digit. Kalkulator menghitung dengan bilangan bulat yang tepat di peramban Anda, jadi jawabannya tepat sepanjang apa pun, dan tidak ada yang dikirim ke mana pun.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor