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\equiv 9\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(17,276)=1$

2. Persamaan $17x\equiv 9\left(\text{mod 276}\right)$ ekivalen dengan $17x-276k=9$ atau diperoleh $x={\displaystyle \frac{9+276k}{17}}$ . dengan mengambil Nilai $x=2$ , menyebabkan $x=33$

3. Solusinya adalah $x\equiv 33\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 $a{a}_k\equiv b\left(\text{mod }{n}_i\right)$ , $k=1,2,..r$ Untuk mendapatkan nilai $a_i$

3. Cari $N_k={\displaystyle \frac{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
$$\overline{x}=(a_1{N}_1{x}_1+a_2{N}_2{x}_2+\cdots +a_r{N}_r{x}_r)\text{(mod }n)$$

Dengan Teorema Sisa Cina,

1. faktorisasi prima dari $276$ adalah $2^2\cdot 3\cdot 23$. Jadi $276=3\cdot 4\cdot 23$. Dengan demikian diperoleh $n=276$, $n_1=3$, $n_2=4$ dan $n_3=23$

2. Selesaikan system $17a_k\equiv 9\text{(mod }{n}_k)$ , $k=1,2,3$, yaitu system$$17a_1\equiv 9\text{(mod }3)\text{dengan k=14 diperoleh}{a}_1=3$$$$17a_2\equiv 9\text{(mod }4)\text{dengan k=19 diperoleh}{a}_2=5$$$$17a_3\equiv 9\text{(mod }23)\text{dengan k=7 diperoleh}{a}_3=10$$3. Cari nilai $N_k={\displaystyle \frac{n}{n_k}}$ dengan $k=1,2,3,...$ yaitu $N_1={\displaystyle \frac{n}{n_1}}={\displaystyle \frac{276}{3}}=92$, $N_2={\displaystyle \frac{n}{n_2}}={\displaystyle \frac{276}{4}}=69$ dan $N_3={\displaystyle \frac{n}{n_3}}={\displaystyle \frac{276}{23}}=12$. Selsaikan sistem $N_k{x}_k\equiv 1\text{(mod }{n}_k)$ yaitu :$$92x_1\equiv 1\text{(mod }3)\text{diperoleh }{x}_1=2$$$$69x_2\equiv 1\text{(mod }4)\text{diperoleh }{x}_2=1$$$$12x_3\equiv 1\text{(mod }23)\text{diperoleh }{x}_3=2$$4. Solusinya adalah$$\begin{array}{rcl}\overline{x}& \equiv & (a_1{N}_1{x}_1+a_2{N}_2{x}_2+a_3{N}_3{x}_3)\text{(mod }n)\\ & \equiv & (3\cdot 92\cdot 2+5\cdot 68\cdot 1+10\cdot 12\cdot 2)\text{(mod }276)\\ & \equiv & 1137\text{(mod }276)\\ & \equiv & 33\text{(mod }276)\end{array}$$

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 :

• Bukti dan penerapan Teorema sisa cina
• Teorema Sisa Cina