Menyelesaikan Persamaan kongruen linier dengan Teorema Sisa Cina
Halo sobat blogger. Kali ini blog matematika akan membagikan sedikit postingan tentang bagaimana cara menyelesaikan persamaan kongkuren linier dengan menggunakan teorema Sisa Cina (CRT).
Pada Postingan sebelumnya saya sudah membahas tentang teorema sisa cina dan cara menyelesaikannya. Nah kali ini akan kita perluas dengan persamaan kongruen linier. Bagaimana cara menyelesaikannya ?
Sebagai contoh.
Selesaikan persamaan linier kongruen $17x\equiv9\left(\text{mod 276}\right)$
Soal diatas dapat kita selesaikan dengan dua cara yaitu dengan cara aljabar biasa dan menggunakan teorema sisa cina. Nah kali ini akan kita bahas dua-duanya yah. Ayo Kita mulai saja
1. karena $gcd\left(17,276\right)=1$
2. Persamaan $17x\equiv9\left(\text{mod 276}\right)$ ekivalen dengan $17x-276k=9$ atau diperoleh $x=\dfrac{9+276k}{17}$ . dengan mengambil Nilai $x=2$ , menyebabkan $x=33$
3. Solusinya adalah $x\equiv33\left(\text{mod 276}\right)$
# Dengan Teorema sisa cina, langkah penyelesaian jika persamaan kongruen linier yang diketahui:
1.Dari persamaan kongruen linier $ax\equiv b\left(\text{mod }n\right)$, maka cari faktorisasi prima dari $n$, yaitu $n=n_{1}n_{2}..n_{r}$ dengan $n_{i}$ adalah prima, $i=1,2,....r$
2. Selesaikan system $aa_{k}\equiv b\left(\text{mod }n_{i}\right)$ , $k=1,2,..r$ Untuk mendapatkan nilai $a_{i}$
3. Cari $N_{k}=\dfrac{n}{n_{k}}$ dengan $i=1,2,...,r$ dan selesaikan system $N_{k}x_{k}\equiv\text{1(mod }n_{k})$ untuk mendapatkan nilai $x_{k}$.
4. Solusinya adalah
$$\bar{x}=\left(a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+\cdots+a_{r}N_{r}x_{r}\right)\text{(mod }n)$$
1. faktorisasi prima dari $276$ adalah $2^{2}\cdot3\cdot23$. Jadi $276=3\cdot4\cdot23$. Dengan demikian diperoleh $n=276$, $n_{1}=3$, $n_{2}=4$ dan $n_{3}=23$
2. Selesaikan system $17a_{k}\equiv9\text{(mod }n_{k})$ , $k=1,2,3$, yaitu system\[ 17a_{1}\equiv9\text{(mod }3)\,\,\,\,\,\,\,\text{dengan k=14 diperoleh}\, a_{1}=3 \]\[17a_{2}\equiv9\text{(mod }4)\,\,\,\,\,\,\,\text{dengan k=19 diperoleh}\, a_{2}=5 \]\[17a_{3}\equiv9\text{(mod }23)\,\,\,\,\,\,\,\text{dengan k=7 diperoleh}\, a_{3}=10 \]3. Cari nilai $N_{k}=\dfrac{n}{n_{k}}$ dengan $k=1,2,3,...$ yaitu $N_{1}=\dfrac{n}{n_{1}}=\dfrac{276}{3}=92$, $N_{2}=\dfrac{n}{n_{2}}=\dfrac{276}{4}=69$ dan $N_{3}=\dfrac{n}{n_{3}}=\dfrac{276}{23}=12$. Selsaikan sistem $N_{k}x_{k}\equiv1\text{(mod }n_{k})$ yaitu :\[ 92x_{1}\equiv1\text{(mod }3)\,\,\,\,\,\text{diperoleh }x_{1}=2 \]\[69x_{2}\equiv1\text{(mod }4)\,\,\,\,\,\text{diperoleh }x_{2}=1 \]\[12x_{3}\equiv1\text{(mod }23)\,\,\,\,\,\text{diperoleh }x_{3}=2 \]4. Solusinya adalah\begin{eqnarray*} \bar{x} & \equiv & \left(a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+a_{3}N_{3}x_{3}\right)\text{(mod }n)\\ & \equiv & \left(3\cdot92\cdot2+5\cdot68\cdot1+10\cdot12\cdot2\right)\text{(mod }276)\\ & \equiv & 1137\text{(mod }276)\\ & \equiv & 33\text{(mod }276)\end{eqnarray*}
Nah sobat blogger mau coba yang man ? silahkan
Baca Juga :
Pada Postingan sebelumnya saya sudah membahas tentang teorema sisa cina dan cara menyelesaikannya. Nah kali ini akan kita perluas dengan persamaan kongruen linier. Bagaimana cara menyelesaikannya ?
Sebagai contoh.
Selesaikan persamaan linier kongruen $17x\equiv9\left(\text{mod 276}\right)$
Soal diatas dapat kita selesaikan dengan dua cara yaitu dengan cara aljabar biasa dan menggunakan teorema sisa cina. Nah kali ini akan kita bahas dua-duanya yah. Ayo Kita mulai saja
# Dengan cara biasa (solusi persamaan kongruen linier),
1. karena $gcd\left(17,276\right)=1$
2. Persamaan $17x\equiv9\left(\text{mod 276}\right)$ ekivalen dengan $17x-276k=9$ atau diperoleh $x=\dfrac{9+276k}{17}$ . dengan mengambil Nilai $x=2$ , menyebabkan $x=33$
3. Solusinya adalah $x\equiv33\left(\text{mod 276}\right)$
# Dengan Teorema sisa cina, langkah penyelesaian jika persamaan kongruen linier yang diketahui:
1.Dari persamaan kongruen linier $ax\equiv b\left(\text{mod }n\right)$, maka cari faktorisasi prima dari $n$, yaitu $n=n_{1}n_{2}..n_{r}$ dengan $n_{i}$ adalah prima, $i=1,2,....r$
2. Selesaikan system $aa_{k}\equiv b\left(\text{mod }n_{i}\right)$ , $k=1,2,..r$ Untuk mendapatkan nilai $a_{i}$
3. Cari $N_{k}=\dfrac{n}{n_{k}}$ dengan $i=1,2,...,r$ dan selesaikan system $N_{k}x_{k}\equiv\text{1(mod }n_{k})$ untuk mendapatkan nilai $x_{k}$.
4. Solusinya adalah
$$\bar{x}=\left(a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+\cdots+a_{r}N_{r}x_{r}\right)\text{(mod }n)$$
Dengan Teorema Sisa Cina,
1. faktorisasi prima dari $276$ adalah $2^{2}\cdot3\cdot23$. Jadi $276=3\cdot4\cdot23$. Dengan demikian diperoleh $n=276$, $n_{1}=3$, $n_{2}=4$ dan $n_{3}=23$
2. Selesaikan system $17a_{k}\equiv9\text{(mod }n_{k})$ , $k=1,2,3$, yaitu system\[ 17a_{1}\equiv9\text{(mod }3)\,\,\,\,\,\,\,\text{dengan k=14 diperoleh}\, a_{1}=3 \]\[17a_{2}\equiv9\text{(mod }4)\,\,\,\,\,\,\,\text{dengan k=19 diperoleh}\, a_{2}=5 \]\[17a_{3}\equiv9\text{(mod }23)\,\,\,\,\,\,\,\text{dengan k=7 diperoleh}\, a_{3}=10 \]3. Cari nilai $N_{k}=\dfrac{n}{n_{k}}$ dengan $k=1,2,3,...$ yaitu $N_{1}=\dfrac{n}{n_{1}}=\dfrac{276}{3}=92$, $N_{2}=\dfrac{n}{n_{2}}=\dfrac{276}{4}=69$ dan $N_{3}=\dfrac{n}{n_{3}}=\dfrac{276}{23}=12$. Selsaikan sistem $N_{k}x_{k}\equiv1\text{(mod }n_{k})$ yaitu :\[ 92x_{1}\equiv1\text{(mod }3)\,\,\,\,\,\text{diperoleh }x_{1}=2 \]\[69x_{2}\equiv1\text{(mod }4)\,\,\,\,\,\text{diperoleh }x_{2}=1 \]\[12x_{3}\equiv1\text{(mod }23)\,\,\,\,\,\text{diperoleh }x_{3}=2 \]4. Solusinya adalah\begin{eqnarray*} \bar{x} & \equiv & \left(a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+a_{3}N_{3}x_{3}\right)\text{(mod }n)\\ & \equiv & \left(3\cdot92\cdot2+5\cdot68\cdot1+10\cdot12\cdot2\right)\text{(mod }276)\\ & \equiv & 1137\text{(mod }276)\\ & \equiv & 33\text{(mod }276)\end{eqnarray*}
Kesimpulan
Dengan cara biasa kelihatannya lebih mudah. Tetapi Teorema sisa cina juga bisa kita aplikasikan dalam Menyelesaikan Persamaan kongruen linier.
Nah sobat blogger mau coba yang man ? silahkan
Baca Juga :
Posting Komentar untuk "Menyelesaikan Persamaan kongruen linier dengan Teorema Sisa Cina"