Selang terbatas

Sistem kekongruenan simultan

Teorema sisa Tiongkok juga dapat dinyatakan dengan menggunakan kekongruenan

Isomorfisma gelanggang

Berdasarkan sudut pandang ini, maka untuk melakukan serangkaian operasi aritmetika pada ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$, teorema sisa Tiongkok memungkinkan untuk melakukan perhitungan serupa pada masing-masing ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$ lalu memperoleh hasil akhirnya dengan menerapkan isomorfismanya (dari kanan ke kiri). Proses ini mungkin saja jauh lebih cepat dibandingkan perhitungan langsung, jika nilai ${\displaystyle N}$ dan banyaknya operasi cukup besar.

Ketunggalan

Misalkan ${\displaystyle x}$ dan ${\displaystyle y}$ merupakan penyelesaian dari sistem kekongruenan linier yang diberikan. Oleh karena ${\displaystyle x}$ dan ${\displaystyle y}$ memiliki sisa pembagian yang sama ketika dibagi oleh ${\displaystyle n_{i}}$, maka selisih antar keduanya (yaitu ${\displaystyle x-y}$) merupakan kelipatan dari ${\displaystyle n_{i}}$, untuk sembarang ${\displaystyle i\in \left\{1,\,2,\,3,\,\ldots ,\,k\right\}}$. Diketahui bahwa ${\displaystyle n_{i}}$ koprima dengan ${\displaystyle n_{j}}$ untuk setiap ${\displaystyle 1\leq i<j\leq k}$, maka ${\displaystyle N}$ juga merupakan faktor dari ${\displaystyle x-y}$, sehingga ${\displaystyle x}$ dan ${\displaystyle y}$ akan kongruen dalam modulo ${\displaystyle N}$. Jika ${\displaystyle x}$ dan ${\displaystyle y}$ bernilai nonnegatif dan kurang dari ${\displaystyle N}$ (seperti pada isi pernyataan pertama), maka ${\displaystyle x-y}$ haruslah bernilai ${\displaystyle 0}$.

Kewujudan (bukti pertama)

Perhatikan bahwa pemetaan $${\displaystyle f(x{\bmod {N}})=\left(x{\bmod {n}}_{1},\,x{\bmod {n}}_{2},\,x{\bmod {n}}_{3},\,\ldots ,\,x{\bmod {n}}_{k}\right)}$$ memetakan kelas-kelas kekongruenan modulo ${\displaystyle N}$ ke barisan kelas-kelas kekongruenan modulo ${\displaystyle n_{i}}$. Bukti ketunggalan menunjukkan bahwa pemetaan tersebut bersifat injektif. Oleh karena domain dari pemetaan tersebut memiliki kardinalitas yang sama dengan kodomainnya, maka pemetaan tersebut juga bersifat surjektif, sehingga penyelesaiannya terjamin ada.

Pembuktian ini cukup sederhana, tetapi tidak menyediakan metode atau cara untuk mencari penyelesaiannya. Selain itu, pembuktian ini tidak dapat diperumum ke situasi lain, berbeda dengan kedua bukti berikut.

Kewujudan (bukti kedua)

Kewujudan penyelesaian dari sistem kongruensinya dapat dilakukan dengan konstruksi bilangan ${\displaystyle x}$ secara eksplisit.^[13] Konstruksi ini melibatkan dua langkah berbeda, yaitu penyelesaian untuk kasus dua moduli, kemudian memperumum penyelesaian tersebut untuk sembarang ${\displaystyle k}$ moduli menggunakan induksi matematika.

Diberikan sistem kekongruenan linier $${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\end{aligned}}}$$ dengan ${\displaystyle n_{1}}$ koprima dengan ${\displaystyle n_{2}}$. Berdasarkan identitas Bézout, maka terdapat bilangan bulat ${\displaystyle p}$ dan ${\displaystyle q}$ sedemikian sehingga $${\displaystyle pn_{1}+qn_{2}=1}$$ Nilai dari ${\displaystyle p}$ dan ${\displaystyle q}$ dapat dicari dengan menggunakan algoritma Euclid diperluas.

Pandang bilangan

$${\displaystyle x=a_{1}qn_{2}+a_{2}pn_{1}}$$

Perhatikan bahwa $${\displaystyle {\begin{aligned}x&=a_{1}(qn_{2})+a_{2}pn_{1}\\&=a_{1}\left(1-pn_{1}\right)+a_{2}pn_{1}\\&=a_{1}+\left(a_{2}-a_{1}\right)pn_{1}\\x&\equiv a_{1}{\pmod {n_{1}}}\\\\x&=a_{1}qn_{2}+a_{2}(pn_{1})\\&=a_{1}qn_{2}+a_{2}\left(1-qn_{2}\right)\\&=a_{2}+\left(a_{1}-a_{2}\right)qn_{2}\\x&\equiv a_{2}{\pmod {n_{2}}}\end{aligned}}}$$ yang menunjukkan bahwa ${\displaystyle x}$ merupakan penyelesaian dari sistem yang diberikan.

Sekarang tinjau sistem kekongruenan linier $${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$$ dengan ${\displaystyle \operatorname {FPB} (a_{i},\,a_{j})=1}$ untuk setiap ${\displaystyle 1\leq i<j\leq k}$. Telah ditunjukkan sebelumnya bahwa dua kekongruenan pertama memiliki suatu penyelesaian, yaitu ${\displaystyle a_{1,\,2}}$. Himpunan penyelesaian dari dua kekongruenan pertama ini ialah himpunan semua bilangan bulat ${\displaystyle x}$ yang memenuhi $${\displaystyle x\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}}$$

Oleh karena ${\displaystyle n_{1}\cdot n_{2}}$ koprima dengan setiap ${\displaystyle n_{i}}$ lainnya, maka sistem kekongruenannya tereduksi menjadi ${\displaystyle k-1}$ kekongruenan simultan, yaitu $${\displaystyle {\begin{aligned}x&\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$$ Penyelesaian sistemnya akan diperoleh dengan melakukan iterasi serupa yang berulang sebanyak ${\displaystyle k-2}$ kali.

Kewujudan (bukti ketiga)

Untuk mengonstruksikan penyelesaian, induksi pada banyaknya moduli tidaklah diperlukan. Namun, konstruksi langsung semacam ini akan melibatkan perhitungan yang lebih rumit dengan bilangan besar, yang membuat metode ini kurang efisien serta jarang digunakan. Walaupun demikian, interpolasi Lagrange merupakan kasus khusus dari konstruksi ini, yang diterapkan pada polinomial alih-alih bilangan bulat.

Misalkan ${\displaystyle N_{i}={\tfrac {N}{n_{i}}}}$ menyatakan darab dari semua moduli selain ${\displaystyle n_{i}}$. Oleh karena setiap ${\displaystyle n_{i}}$ koprima pasang demi pasang, maka ${\displaystyle N_{i}}$ akan koprima dengan ${\displaystyle n_{i}}$. Berdasarkan identitas Bézout, maka terdapat suatu bilangan bulat ${\displaystyle M_{i}}$ dan ${\displaystyle m_{i}}$ sedemikian sehingga $${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1}$$

Pandang bilangan $${\displaystyle x=a_{1}M_{1}N_{1}+a_{2}M_{2}N_{2}+a_{3}M_{3}N_{3}+\ldots +a_{k}M_{k}N_{k}}$$ Jika ${\displaystyle i\neq j}$, maka berdasarkan definisi dari ${\displaystyle N_{i}}$, perhatikan bahwa ${\displaystyle N_{i}}$ merupakan kelipatan dari ${\displaystyle n_{j}}$. Akibatnya, $${\displaystyle {\begin{aligned}x&=a_{1}M_{1}N_{1}+a_{2}M_{2}N_{2}+a_{3}M_{3}N_{3}+\ldots +a_{k}M_{k}N_{k}\\x&\equiv a_{j}M_{j}N_{j}{\pmod {n_{j}}}\\&\equiv a_{j}(1-m_{j}n_{j}){\pmod {n_{j}}}\\&\equiv a_{j}{\pmod {n_{j}}}\end{aligned}}}$$ untuk setiap ${\displaystyle 1\leq j\leq k}$, sehingga ${\displaystyle x}$ merupakan penyelesaian dari sistem yang diberikan.