Kalkulator Teorema Sisa Cina

Selamat datang di Kalkulator Teorema Sisa Cina, alat teori bilangan hebat yang menyelesaikan sistem kongruensi simultan menggunakan Teorema Sisa Cina (CRT). Baik Anda sedang mempelajari aritmatika modular, mempersiapkan kompetisi matematika, mengerjakan masalah kriptografi, atau menjelajahi teori bilangan, kalkulator ini menyediakan solusi langkah demi langkah lengkap dengan visualisasi interaktif yang menunjukkan bagaimana kelas kongruensi selaras pada solusi unik.

Apa itu Teorema Sisa Cina?

Teorema Sisa Cina (CRT) adalah hasil fundamental dalam teori bilangan yang menjamin keberadaan dan keunikan solusi untuk sistem kongruensi simultan, asalkan moduli adalah koprima berpasangan. Teorema ini pertama kali dijelaskan oleh matematikawan Cina Sunzi (孫子) dalam karyanya Sunzi Suanjing (孫子算經) sekitar abad ke-3 Masehi.

Secara formal, diberikan sistem:

Jika semua moduli \(m_1, m_2, \ldots, m_k\) adalah koprima berpasangan (artinya, \(\gcd(m_i, m_j) = 1\) untuk semua \(i \neq j\)), maka terdapat solusi unik \(x\) modulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

Cara Kerja Algoritma CRT

Bukti konstruktif menyediakan algoritma yang digunakan oleh kalkulator ini:

Langkah 1: Hitung M

Hitung hasil kali semua moduli:

Langkah 2: Hitung setiap Mᵢ

Untuk setiap kongruensi \(i\), hitung \(M_i = M / m_i\). Ini adalah hasil kali semua moduli kecuali \(m_i\).

Langkah 3: Cari Invers Modular

Untuk setiap \(i\), cari \(y_i\) sedemikian hingga \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) menggunakan Algoritma Euclidean yang Diperluas. Karena \(M_i\) dan \(m_i\) adalah koprima (semua moduli adalah koprima berpasangan), invers ini selalu ada.

Langkah 4: Susun Solusi

Solusi umum adalah \(x + k \cdot M\) untuk setiap bilangan bulat \(k\), yang berarti solusi berulang setiap \(M\) bilangan bulat.

Cara Menggunakan Kalkulator Ini

1. Masukkan kongruensi Anda: Untuk setiap persamaan \(x \equiv a \pmod{m}\), masukkan sisa \(a\) dan modulus \(m\). Mulailah dengan 2 kongruensi dan klik "Tambah Kongruensi" untuk menambah lebih banyak (hingga 10).
2. Periksa moduli Anda: Semua moduli harus berupa bilangan bulat positif ≥ 2 dan koprima berpasangan. Kalkulator memverifikasi ini secara otomatis.
3. Klik "Selesaikan Sistem": Kalkulator menerapkan algoritma CRT dan menunjukkan solusi unik beserta pengerjaan langkah demi langkah.
4. Tinjau visualisasi: Garis bilangan menunjukkan bagaimana kelas kongruensi dari setiap persamaan berpotongan pada solusi.
5. Verifikasi: Bagian verifikasi mengonfirmasi bahwa solusi memenuhi setiap kongruensi asli.

Memahami Hasil

• Solusi Non-Negatif Terkecil (x₀): Solusi unik dalam rentang [0, M−1]
• Solusi Umum: Semua bilangan bulat dalam bentuk x₀ + kM di mana k adalah bilangan bulat apa pun
• Tabel Verifikasi: Mengonfirmasi x₀ mod mᵢ = aᵢ untuk setiap kongruensi
• Rincian Langkah demi Langkah: Menunjukkan Mᵢ, invers modular yᵢ, dan jumlah parsial aᵢ·Mᵢ·yᵢ untuk setiap persamaan
• Garis Bilangan: Representasi visual tentang bagaimana kelas sisa selaras pada solusi

Aplikasi Teorema Sisa Cina

Masalah Sunzi yang Klasik

Masalah asli dari Sunzi Suanjing bertanya: "Ada benda-benda tertentu yang jumlahnya tidak diketahui. Jika kita menghitungnya dengan tiga, ada dua yang tersisa; dengan lima, tiga yang tersisa; dan dengan tujuh, dua yang tersisa. Berapa banyak benda yang ada?"

Ini diterjemahkan menjadi: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Menggunakan CRT, jawabannya adalah x = 23 (dan secara umum, 23 + 105k untuk setiap bilangan bulat non-negatif k).

Kapan CRT Tidak Berlaku?

• Moduli tidak koprima: Jika ada sepasang moduli yang berbagi faktor persekutuan lebih besar dari 1, CRT standar tidak menjamin adanya solusi. Solusi mungkin masih ada jika sisa-sisanya kompatibel, tetapi kalkulator ini memerlukan moduli koprima berpasangan untuk algoritma standar.
• Kongruensi tunggal: CRT memerlukan setidaknya 2 kongruensi. Sebuah kongruensi tunggal \(x \equiv a \pmod{m}\) sudah memiliki solusi trivial x = a.

Algoritma Euclidean yang Diperluas

Algoritma Euclidean yang Diperluas sangat penting untuk CRT karena algoritma ini menemukan invers modular. Diberikan bilangan bulat \(a\) dan \(b\), algoritma ini menemukan bilangan bulat \(x\) dan \(y\) sedemikian hingga:

Ketika \(\gcd(a, b) = 1\), maka \(x\) adalah invers modular dari \(a\) modulo \(b\), yaitu, \(a \cdot x \equiv 1 \pmod{b}\).

Pertanyaan yang Sering Diajukan

Apa itu Teorema Sisa Cina?

Teorema Sisa Cina (CRT) menyatakan bahwa jika Anda memiliki sistem kongruensi simultan x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), di mana semua moduli adalah koprima berpasangan, maka terdapat solusi unik modulo M = m₁ × m₂ × ... × mₖ. Teorema ini pertama kali dijelaskan oleh matematikawan Cina Sunzi pada abad ke-3.

Apa yang dimaksud dengan koprima berpasangan?

Koprima berpasangan berarti setiap pasangan moduli tidak memiliki faktor persekutuan selain 1. Misalnya, {3, 5, 7} adalah koprima berpasangan karena fpb(3,5)=1, fpb(3,7)=1, dan fpb(5,7)=1. Namun, {4, 6, 5} BUKAN koprima berpasangan karena fpb(4,6)=2.

Bagaimana cara menyelesaikan sistem kongruensi langkah demi langkah?

Untuk menyelesaikan menggunakan CRT: (1) Verifikasi semua moduli adalah koprima berpasangan. (2) Hitung M = hasil kali semua moduli. (3) Untuk setiap kongruensi, hitung Mᵢ = M/mᵢ. (4) Temukan invers modular yᵢ dari Mᵢ modulo mᵢ menggunakan Algoritma Euclidean yang Diperluas. (5) Hitung solusi x = Σ(aᵢ × Mᵢ × yᵢ) mod M. Solusi umumnya adalah x + k×M untuk setiap bilangan bulat k.

Apa saja aplikasi Teorema Sisa Cina?

CRT memiliki banyak aplikasi praktis: Kriptografi RSA menggunakan CRT untuk dekripsi yang efisien. Ilmu komputer menggunakannya untuk aritmatika bilangan besar dengan memecah perhitungan menjadi potongan modular yang lebih kecil. Pemrosesan sinyal menerapkan CRT dalam kode pengoreksi kesalahan. Masalah penjadwalan dan kalender di mana peristiwa berulang pada interval yang berbeda juga menggunakan CRT.

Apa yang terjadi jika moduli tidak koprima?

Jika moduli tidak koprima berpasangan, CRT standar tidak berlaku secara langsung. Dalam beberapa kasus, solusi mungkin masih ada jika kondisi kompatibilitas tertentu terpenuhi (sisa harus konsisten modulo FPB dari moduli yang tidak koprima). Namun, jika tidak ada solusi, sistem kongruensi tersebut tidak konsisten.

Sumber Daya Tambahan

• Teorema Sisa Cina - Wikipedia
• Algoritma Euclidean yang Diperluas - Wikipedia
• Aritmatika Modular - Wikipedia