Teorema Sisa Cina

7:15:00 PM
Pada kesempatan kali ini saya akan membuat postingan tentang teorema sisa cina. Apa itu ?? Teorema sisa cina atau biasa di kenal dengan istilah Chinese Remainder Theorem (CRT) Adalah suatu teorema penting dalam teori bilangan yang bisa di gunakan dalam pemecahan masalah olimpiade matematika bidang teori bilangan. Penjelasan Teorema tersebut bisa di lihat penjelasan dibawah.


Misalkan $n_{1},n_{2},\ldots n_{r}$ bilangan bulat positif sehingga gcd$(n_{i},n_{j})=1$ untuk $i\neq j$. Maka sistem kongruensi linier satu variabel berikut

\begin{eqnarray*}
x & \equiv & a_{1}\,\text{(mod }n_{1})\\
x & \equiv & a_{2}\,\text{(mod }n_{2})\\
& \vdots\\
x & \equiv & a_{r}\,\text{(mod }n_{r})
\end{eqnarray*}

Untuk pembuktiannya silahkan anda lihat dalam buku teks teori bilangan.
Sekarang pasti teman-teman bertanya-tanya untuk apa teorema itu dan apa aplikasinya dalam teori bilangan terutama dalam matematika. Menjawab pertanyaan tersebut lihatlah contoh berikut. Mudah-mudahan bisa menjawabnya.


Kami adalah keluarga bilangan bulat postitif. Jika kami dibagi 6 memberikan sisa 5, dibagi 11 memberikan sisa 4 dan dibagi 17 memberikan sisa 3.


1. Tentukan bentuk umum kami

2. Tentukan tiga anggota terkecil dari kami.


Penyelesaian :


Menjawab soal diatas sebenarnya dapat dilakukan dengan cara coba-coba. Tetapi berapa kali kita harus mencoba ? Jalan lain adalah dengan menggunakan Teorema Sisa Cina diatas. Perhatikan langkah-langkahnya berikut:


Misalkan kami adalah $x$

\begin{eqnarray*}
x & \equiv & 5\,(\text{mod 6)}\\
x & \equiv & 4\,\text{(mod 11)}\\
x & \equiv & 3\,(\text{mod 17)}
\end{eqnarray*}
Dengan menggunakan teorema sisa Cina kita mendapatkan

\begin{eqnarray*}
n & = & 6\cdot11\cdot17\\
& = & 1122
\end{eqnarray*}
\begin{eqnarray*}
N_{1} & = & \frac{n}{6}=\frac{1122}{6}=187\\
N_{2} & = & \frac{n}{11}=\frac{1122}{11}=102\\
N_{3} & = & \frac{n}{17}=\frac{1122}{17}=66
\end{eqnarray*}
\begin{eqnarray*}
187x & \equiv & 1\,\text{(mod 6)}\Rightarrow x_{1}=1\\
102x & \equiv & 1\,\text{(mod 11)}\Rightarrow x_{2}=4\\
66x & \equiv & 1\,(\text{mod 17)}\Rightarrow x_{3}=8
\end{eqnarray*}
\begin{eqnarray*}
x & = & 5\cdot187\cdot1+4\cdot102\cdot4+3\cdot66\cdot8\\
& = & 935+1632+1584\\
& = & 4151
\end{eqnarray*}
\begin{eqnarray*}
x & \equiv & 4151\text{ (mod 1122)}\\
x & \equiv & 785\text{ (mod 1122)}
\end{eqnarray*}

1. Bentuk umumnya adalah $x\equiv785\text{ (mod 1122) }$atau $x=785+1122t$ dengan $t=0,1,2,\ldots$

2. Tiga anggota terkecil dari kami adalah
a. $x=785+0=785$
b. $x=785+1122=1907$
c. $x=785+1122(2)=785+2244=3029$


 Sekian yah........

Artikel Terkait

Next Article
« Prev Post
Previous Article
Next Post »