Bukti dan Penerapan Teorema Sisa Cina
Halo sobat blogger. Sudah lama rasanya tidak menulis artikel tentang matematika. Pada kesempatan kali ini saya akan membuat postingan tentang bukti dari teorema sisa cina. Tetapi sebelum kita lanjut, silahkan buka artikel kami sebelumnya di Teorema sisa Cina.
Dalam artikel tersebut, saya membuat sedikit contoh penggunaan teorema sisa cina. Tetapi hanya sebatas contoh dan pembahasan. Juga saya berikan teorema nya tetapi tidak sempat saya buktikan.
Nah kesempatan kali ini saya akan membuat bukti dari teorema sisa cina yang sangat terkenal di teori bilangan.
Teorema sisa Cina atau biasa di kenal dengan Chinese Remainder Theorem adalah hasil tentang Kongruen di teori bilangan dan digeneralisasi dalam aljabar abstrak yang Pertama kali dipublikasikan pada abad ke-3 sampai abad ke-5 oleh Sun Tzu seorang matematikawan Cina.
Dalam publikasi tersebut diperkenalkan metode mencari solusi sistem linear kongkruen, yang sekarang kita kenal dengan Teorema Sisa Cina (Chinese remainder theorem) bisa disingkat CRT.
Pada Awalnya, Teorema Sisa Cina, pertama kali diperkenalkan karena adanya teka-teki Cina kuno. Teka-teki tersebut adalah sebagai berikut
Ada beberapa bilangan yang tidak diketahui. Bilangan itu dibagi 3, sisanya adalah 2; Bilangan itu dibagi oleh 5, sisanya adalah 3; Bilangan itu dibagi oleh 7 sisanya adalah 2; Bilangan apakah itu?
Dalam notasi matematika pernyataan diatas dapat kita tuliskan sebagai berikut :
$x \equiv 2 \text{(mod } 3)$
$x \equiv 3 \text{(mod } 5)$
$x \equiv 2 \text{(mod } 7)$
Sebelum kita mulai pembahasan, alangkah baiknya kita sajikan dulu teorema sisa cina yang sudah saya tulis dalam artikel sebelumnya. Berikut Teoremanya.
Teorema Sisa Cina : 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*}mempunyai solusi simultan, yang tunggal modulo bilangan bulat $n_1,n_2,...n_r$
Buktinya saya ambil dari buku teori bilangan. Sobat bisa memberikan bukti Teorema sisa Cina di kolom komentar jika berbeda dengan bukti yang saya tuliskan berikut.
Bukti : Bentuk Hasil Kali $n=n_1n_2...n_r$. Untuk setiap $k=1,2,..,r$, misalkan $N_k=\dfrac{n}{n_k}=n_1n_2...n_{k-1}n_{k+1}...n_r$. atau $N_k$ adalah hasil kali semua bilangan bulat $n_i$ dengan faktor $n_k$ dihapuskan.
Diketahui bahwa $gcd(n_i,n_j)=1$ untuk $i \neq j$ atau $n_i$ relatif prima dengan $n_j$ untuk $i\neq j$. Dengan demikian diperoleh $gcd(N_k,n_k)=1$
Berdasarkan teori kongruen linier tunggal, hal ini memungkinkan untuk menyelesaikan kongruen $N_kx \equiv 1\text{(mod } n_k)$, sebutlah solusi tunggal $x_k$. Tujuannya adalah untuk membuktikan bahwa bilangan $$\bar{x}=a_1N_1x_1+a_2N_2x_2+...+a_rN_rx_r=a_kN_kx_k \text{(mod } n_k)$$ adalah solusi simultan dari sistem kongruen linier yg diberikan.
Pertama, amati bahwa $N_i \equiv 0 \text{(mod } n_k)$ untuk $ i\neq k$, karena $n_k|N_i$. Hasilnya adalah $$\bar{x}=a_1N_1x_1+a_2N_2x_2+...+a_rN_rx_r=a_kN_kx_k \text{(mod } n_k)$$Tapi $x_k$ bilangan bulat yang dipilih untuk memenuhi kongruen $N_kx \equiv 1 \text{(mod } n_k)$, yang menyebabkan $$\bar{x} \equiv a_k \cdot 1 \equiv a_k \text{(mod } n_k)$$ Ini menunjukkan bahwa solusi untuk sistem kongruen yang diberikan ada.
Untuk menunjukkan ketunggalannya, misalkan $x'$ adalah sebarang bilangan bulat yang memenuhi sistem kongruen ini. Maka $$\bar{x}\equiv a_k\equiv x' \text{(mod } n_k)\,\,\,k = 1,2,3,...,r$$ dan selanjutnya $n_k|\bar{x}-x'$ untuk setiap nilai $k$. Karena $gcd(n_i,n_j)=1$, maka diperoleh $n_1n_2...n_r|\bar{x}-x'$, karenanya $\bar{x}\equiv x'\text{(mod } n_k)$. $\blacksquare$
Dengan Teorema Sisa Cina, maka langkah penyelesaian suatu sistem kongruen linier adalah :
Misalkan system kongruen linier\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*}Maka langkah untuk mencari solusi sistem ini:
# Contoh :
$x \equiv 2 \text{(mod } 3)$
$x \equiv 4 \text{(mod } 5)$
Perhatikan bahwa sistem Persamaan ini terdiri dari 3 persamaan konruen linier, jadi $k=1,2,3$. Dari sistem persamaan diperoleh $a_{1}=3,a_{2}=2,a_{3}=4,n_{1}=4,n_{2}=3,n_{3}=5$
$15x_{1}\equiv1\text{ (mod }4)$ ekuivalen dengan $15x_{1}-1=4k$ Diperoleh $x_{1}=\dfrac{1+4k}{15}$. Nilai $k=11$ menyebabkan $x_{1}=3$. dengan cara yang sama diperoleh $x_{2}=2$, dan $x_{3}=3$
Solusinya adalah
\begin{eqnarray*}
\bar{x} & = & \left(a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+a_{3}N_{3}x_{3}\right)\left(\text{mod }n\right)\\
& = & \left(3\cdot15\cdot3+2\cdot20\cdot2+4\cdot12\cdot3\right)\left(\text{mod }60\right)\\
& = & 359\left(\text{mod }60\right)\\
& = & 59\left(\text{mod }60\right)
\end{eqnarray*} Jadi solusi untuk
$x \equiv 3 \text{(mod } 4)$
$x \equiv 2 \text{(mod } 3)$
$x \equiv 4 \text{(mod } 5)$
adalah $\bar{x}\equiv 59 \text{(mod }60)$
# Soal Berikutnya :
Dengan menggunakan Teorema Sisa Cina, carilah solusi untuk sistem kongruen linier berikut:\begin{eqnarray*}x & \equiv & 2\text{ (mod }3)\\x & \equiv & 3\text{ (mod }5)\\x & \equiv & 2\text{ (mod }7)\end{eqnarray*}
Sama dengan soal pertama. Hanya berganti angka saja. Gampang kan ?
Nah bagaimana jika sobat mendapatkan soal berikut
Dalam artikel tersebut, saya membuat sedikit contoh penggunaan teorema sisa cina. Tetapi hanya sebatas contoh dan pembahasan. Juga saya berikan teorema nya tetapi tidak sempat saya buktikan.
Nah kesempatan kali ini saya akan membuat bukti dari teorema sisa cina yang sangat terkenal di teori bilangan.
Teorema sisa Cina atau biasa di kenal dengan Chinese Remainder Theorem adalah hasil tentang Kongruen di teori bilangan dan digeneralisasi dalam aljabar abstrak yang Pertama kali dipublikasikan pada abad ke-3 sampai abad ke-5 oleh Sun Tzu seorang matematikawan Cina.
Dalam publikasi tersebut diperkenalkan metode mencari solusi sistem linear kongkruen, yang sekarang kita kenal dengan Teorema Sisa Cina (Chinese remainder theorem) bisa disingkat CRT.
Pada Awalnya, Teorema Sisa Cina, pertama kali diperkenalkan karena adanya teka-teki Cina kuno. Teka-teki tersebut adalah sebagai berikut
Ada beberapa bilangan yang tidak diketahui. Bilangan itu dibagi 3, sisanya adalah 2; Bilangan itu dibagi oleh 5, sisanya adalah 3; Bilangan itu dibagi oleh 7 sisanya adalah 2; Bilangan apakah itu?
Dalam notasi matematika pernyataan diatas dapat kita tuliskan sebagai berikut :
$x \equiv 2 \text{(mod } 3)$
$x \equiv 3 \text{(mod } 5)$
$x \equiv 2 \text{(mod } 7)$
Bukti Teorema Sisa Cina
Sebelum kita mulai pembahasan, alangkah baiknya kita sajikan dulu teorema sisa cina yang sudah saya tulis dalam artikel sebelumnya. Berikut Teoremanya.
Teorema Sisa Cina : 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*}mempunyai solusi simultan, yang tunggal modulo bilangan bulat $n_1,n_2,...n_r$
Buktinya saya ambil dari buku teori bilangan. Sobat bisa memberikan bukti Teorema sisa Cina di kolom komentar jika berbeda dengan bukti yang saya tuliskan berikut.
Bukti : Bentuk Hasil Kali $n=n_1n_2...n_r$. Untuk setiap $k=1,2,..,r$, misalkan $N_k=\dfrac{n}{n_k}=n_1n_2...n_{k-1}n_{k+1}...n_r$. atau $N_k$ adalah hasil kali semua bilangan bulat $n_i$ dengan faktor $n_k$ dihapuskan.
Diketahui bahwa $gcd(n_i,n_j)=1$ untuk $i \neq j$ atau $n_i$ relatif prima dengan $n_j$ untuk $i\neq j$. Dengan demikian diperoleh $gcd(N_k,n_k)=1$
Berdasarkan teori kongruen linier tunggal, hal ini memungkinkan untuk menyelesaikan kongruen $N_kx \equiv 1\text{(mod } n_k)$, sebutlah solusi tunggal $x_k$. Tujuannya adalah untuk membuktikan bahwa bilangan $$\bar{x}=a_1N_1x_1+a_2N_2x_2+...+a_rN_rx_r=a_kN_kx_k \text{(mod } n_k)$$ adalah solusi simultan dari sistem kongruen linier yg diberikan.
Pertama, amati bahwa $N_i \equiv 0 \text{(mod } n_k)$ untuk $ i\neq k$, karena $n_k|N_i$. Hasilnya adalah $$\bar{x}=a_1N_1x_1+a_2N_2x_2+...+a_rN_rx_r=a_kN_kx_k \text{(mod } n_k)$$Tapi $x_k$ bilangan bulat yang dipilih untuk memenuhi kongruen $N_kx \equiv 1 \text{(mod } n_k)$, yang menyebabkan $$\bar{x} \equiv a_k \cdot 1 \equiv a_k \text{(mod } n_k)$$ Ini menunjukkan bahwa solusi untuk sistem kongruen yang diberikan ada.
Untuk menunjukkan ketunggalannya, misalkan $x'$ adalah sebarang bilangan bulat yang memenuhi sistem kongruen ini. Maka $$\bar{x}\equiv a_k\equiv x' \text{(mod } n_k)\,\,\,k = 1,2,3,...,r$$ dan selanjutnya $n_k|\bar{x}-x'$ untuk setiap nilai $k$. Karena $gcd(n_i,n_j)=1$, maka diperoleh $n_1n_2...n_r|\bar{x}-x'$, karenanya $\bar{x}\equiv x'\text{(mod } n_k)$. $\blacksquare$
Dengan Teorema Sisa Cina, maka langkah penyelesaian suatu sistem kongruen linier adalah :
Misalkan system kongruen linier\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*}Maka langkah untuk mencari solusi sistem ini:
- Periksa $gcd(n_i,n_j)$ untuk $i \neq j$, jika $gcd(n_i,n_j)=1$ maka sistem mempunyai solusi.
- Tentukan $n=n_1n_2...n_r$ dan $N_k=\dfrac{n}{n_k}=n_1n_2...n_{k-1}n_{k+1}...n_r,\,k=1,2,..r$
- Selesaikan $N_kx_k\equiv 1 \text{(mod } n_k), k=1,2,...r$.
- Solusinya adalah $\bar{x}\equiv (a_1N_1x_1+a_2N_2x_2+...+a_rN_rx_r)\text{(mod } n)$
# Contoh :
Dengan Teorema Sisa Cina, carilah solusi untuk sistem kongruen linier berikut :
$x \equiv 3 \text{(mod } 4)$$x \equiv 2 \text{(mod } 3)$
$x \equiv 4 \text{(mod } 5)$
Perhatikan bahwa sistem Persamaan ini terdiri dari 3 persamaan konruen linier, jadi $k=1,2,3$. Dari sistem persamaan diperoleh $a_{1}=3,a_{2}=2,a_{3}=4,n_{1}=4,n_{2}=3,n_{3}=5$
- Oleh karena $$gcd\left(4,3\right)=gcd\left(4,5\right)=gcd\left(3,5\right)=1$$ maka sistem ini punya solusi.
- Nilai $n=n_{1}\cdot n_{2}\cdot n_{3}=4\cdot 3\cdot 5=60$ dan \[N_{1}=\frac{n}{n_{1}}=\frac{60}{4}=15; \]\[N_{2}=\frac{n}{n_{2}}=\frac{60}{3}=20;\]\[N_{3}=\frac{n}{n_{3}}=\frac{60}{5}=12;\]
- Selesaikan $N_{k}x_{i}\equiv1\text{(mod }n_{k}),\,\, k=1,2,3$ yaitu \begin{eqnarray*}15x_{1} & \equiv & 1\text{ (mod }4)\\20x_{2} & \equiv & 1\text{ (mod }3)\\12x_{3} & \equiv & 1\text{ (mod }5)\end{eqnarray*}
$15x_{1}\equiv1\text{ (mod }4)$ ekuivalen dengan $15x_{1}-1=4k$ Diperoleh $x_{1}=\dfrac{1+4k}{15}$. Nilai $k=11$ menyebabkan $x_{1}=3$. dengan cara yang sama diperoleh $x_{2}=2$, dan $x_{3}=3$
Solusinya adalah
\begin{eqnarray*}
\bar{x} & = & \left(a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+a_{3}N_{3}x_{3}\right)\left(\text{mod }n\right)\\
& = & \left(3\cdot15\cdot3+2\cdot20\cdot2+4\cdot12\cdot3\right)\left(\text{mod }60\right)\\
& = & 359\left(\text{mod }60\right)\\
& = & 59\left(\text{mod }60\right)
\end{eqnarray*} Jadi solusi untuk
$x \equiv 3 \text{(mod } 4)$
$x \equiv 2 \text{(mod } 3)$
$x \equiv 4 \text{(mod } 5)$
adalah $\bar{x}\equiv 59 \text{(mod }60)$
# Soal Berikutnya :
Dengan menggunakan Teorema Sisa Cina, carilah solusi untuk sistem kongruen linier berikut:\begin{eqnarray*}x & \equiv & 2\text{ (mod }3)\\x & \equiv & 3\text{ (mod }5)\\x & \equiv & 2\text{ (mod }7)\end{eqnarray*}
Sama dengan soal pertama. Hanya berganti angka saja. Gampang kan ?
Nah bagaimana jika sobat mendapatkan soal berikut
- Selesaikan persamaan linier kongruen $17x\equiv9\text{ (mod }276)$
- Selesaikan persamaan linier kongruen $13x\equiv1\text{ (mod }70)$
Tentu Sobat agak kesulitan. Tetapi sebenarnya sama saja dengan cara diatas. Nah. pada postingan berikutnya akan saya bahas tentang Solusi Sistem Kongruen Linier dengan dua Variabel.
Baca Juga :
Baca Juga :
Posting Komentar untuk "Bukti dan Penerapan Teorema Sisa Cina"