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).

Menyelesaikan Persamaan kongruen linier dengan Teorema Sisa Cina


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 :

0 Response to "Menyelesaikan Persamaan kongruen linier dengan Teorema Sisa Cina"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel