Soal dan Pembahasan - Teorema Sisa Cina

Diperbarui 18 Oktober 2022 — 10 Soal

Teorema Sisa Cina merupakan salah satu teorema penting pada materi teori bilangan, yang digunakan untuk menyelesaikan sistem kongruensi linear. Sesuai namanya, teorema ini mempunyai sejarah yang berkaitan dengan negara Cina.

Sebelum membahas lanjut, mari perhatikan daftar isi berikut.

Sejarah Teorema Sisa Cina

Sesuai namanya, teorema sisa cina berkaitan dengan negara Cina. Masalah tertua yang berkaitan dengan Teorema Sisa Cina termuat dalam karya berjudul Sunzi Suanjing, yang ditulis oleh Matematikawan Cina bernama Sun Zi. Masalah ini termuat dalam volume ketiga, tepatnya pada Problem 26.

Problem 26 dalam Sunzi Suanjing

Kita mempunyai sejumlah objek, tapi tidak diketahui tepatnya ada berapa. Jika kita membaginya dengan $3$, maka bersisa $2$. Jika kita membaginya dengan $5$, maka bersisa $3$. Jika kita membaginya dengan $7$, maka bersisa $2$. Berapakah jumlah objek itu?

Dalam bukunya, Sun Zi memanfaatkan bilangan $70$, $21$, dan $15$. Ia mengalikan sisa pembagian oleh $3$ dengan $70$, sisa pembagian oleh $5$ dengan $21$, dan sisa pembagian oleh $7$ dengan $15$, lalu menjumlahkan hasilnya. $$2 \times 70 + 3 \times 21 + 2 \times 15 = 233$$

Diperoleh bilangan $233$ sebagai solusi. Karena nilainya lebih dari $105$, maka dapat dikurangkan dengan kelipatan $105$, sehingga diperoleh $23$ sebagai solusi terkecil dari masalah tersebut.

Sayangnya, Problem 26 adalah satu-satunya masalah yang berkaitan Teorema Sisa Cina dalam buku Sunzi Suanjing. Karena itu, tidak bisa disimpulkan bahwa Sun Zi menemukan metode umum untuk menyelesaikan masalah serupa.

Metode umum baru ditemukan pada tahun 1247, dalam buku berjudul Shushu Jiuzhang (Mathematical Treatise in Nine Sections), yang ditulis oleh Qin Jiushao.

Bukti Teorema Sisa Cina

Pada bagian ini, kita menggunakan istilah relatif prima. Dua bilangan dikatakan relatif prima, jika FPB-nya adalah $1$. Untuk tiga bilangan atau lebih, dikatakan saling relatif prima, jika setiap pasang bilangan mempunyai FPB $1$.

Teorema Sisa Cina

Misalkan $m_1,m_2,\ldots,m_r$ adalah bilangan bulat positif selain $1$ yang saling relatif prima. Untuk setiap bilangan bulat $a_1,a_2,\ldots,a_r$ sistem kongruensi linear $$\left\{\begin{aligned} x &\equiv a_1 \;(\text{mod } m_1) \\[2pt] x &\equiv a_2 \;(\text{mod } m_2) \\[2pt] &\;\;\vdots \\[2pt] x &\equiv a_r \;(\text{mod } m_r) \end{aligned}\right.$$ mempunyai solusi, dan tiap dua solusi kongruen modulo $m=m_1 \times m_2 \times \ldots \times m_r$.

Kita akan membuktikan teorema di atas. Misalkan $m=m_1 \times m_2 \times \ldots \times m_r$ dan $y_j$ menyatakan hasil bagi antara $m$ dengan $m_j$. Dengan kata lain, $y_j$ merupakan hasil kali semua moduus selain $m_j$.

Karena $m_1,m_2,\ldots,m_r$ saling relatif prima, maka $y_j$ dan $m_j$ juga relatif prima. Akibatnya, terdapat bilangan bulat $z_j$ sedemikian sehingga $$y_jz_j \equiv 1 \;(\text{mod } m_j), \quad j=1,2,\ldots, r$$

Kita akan menunjukkan bahwa nilai $x_0$ berikut merupakan solusi dari sistem kongruensi semula. $$x_0 = a_1y_1z_1+a_2y_2z_2+\ldots+a_ry_rz_r$$

Untuk $i=1,2,\ldots,r$ diperoleh $$x_0 \equiv (a_1y_1z_1+\ldots+ a_iy_iz_i+\ldots+a_ry_rz_r) \;(\text{mod } m_i)$$

Perhatikan bahwa $y_j \equiv 0 \;(\text{mod } m_i)$ untuk $j \neq i$, sehingga $a_jy_jz_j \equiv 0 \;(\text{mod } m_i)$. Akibatnya $$x_0 \equiv a_iy_iz_i \;(\text{mod } m_i)$$

Karena $y_iz_i \equiv 1 \;(\text{mod } m_i)$ maka diperoleh $$\begin{aligned} x_0 &\equiv a_iy_iz_i \;(\text{mod } m_i) \\[2pt] &\equiv a_i \cdot 1 \;(\text{mod } m_i) \\[2pt] &\equiv a_i \;(\text{mod } m_i) \end{aligned}$$

Karena $i=1,2,\ldots,r$ maka dapat disimpulkan bahwa $x_0$ memenuhi setiap kongruensi pada sistem semula. Dengan ini, terbukti bahwa sistem kongruensi tersebut mempunyai solusi.

Berikutnya, akan ditunjukkan bahwa tiap dua solusi kongruen modulo $m$. Misalkan $x_1$ adalah solusi lain dari sistem tersebut. Untuk $i=1,2,\ldots,r$ diperoleh $$x_0 \equiv a_i \;(\text{mod } m_i) \quad \text{dan} \quad x_1 \equiv a_i \;(\text{mod } m_i)$$ sehingga $x_0 \equiv x_1 \;(\text{mod } m_i)$. Hal ini berakibat $$x_0 \equiv x_1 \;(\text{mod } \text{KPK}(m_1,m_2,\ldots,m_r))$$

Karena $m_1,m_2,\ldots,m_r$ saling relatif prima, maka nilai KPK sama dengan hasil kalinya, yaitu $m$. Dengan demikian, $x_0 \equiv x_1 \;(\text{mod } m)$. Terbukti.

Langkah-Langkah Penyelesaian

Sebagai contoh, kita akan menyelesaikan sistem kongruensi pada Problem 26. $$\left\{\begin{aligned} x &\equiv 2 \;(\text{mod } 3) \\[2pt] x &\equiv 3 \;(\text{mod } 5) \\[2pt] x &\equiv 2 \;(\text{mod } 7) \end{aligned}\right.$$

Langkah 1. Periksa apakah modulus dalam sistem tersebut saling relatif prima.

Langkah ini digunakan untuk mengecek apakah Teorema Sisa Cina bisa diterapkan. Modulus-modulus yang ada dalam sistem adalah $\textcolor{red}{3}$, $\textcolor{green}{5}$, dan $\textcolor{blue}{7}$. Karena ketiganya saling relatif prima, maka sistem tersebut mempunyai solusi berdasarkan Teorema Sisa Cina.

Langkah 2. Tentukan nilai $m$ dan $y_i$ untuk $i=1,2,\ldots,r$.

Nilai $m$ diperoleh dari perkalian semua modulus, sedangkan $y_i$ diperoleh dari hasil bagi $m$ dengan $m_i$. Untuk kongruensi dalam soal, diperoleh $m=\textcolor{red}{3} \times \textcolor{green}{5} \times \textcolor{blue}{7}=105$ dan $$\begin{aligned} y_1 &= \frac{105}{\textcolor{red}{3}} = 35 \\[2pt] y_2 &= \frac{105}{\textcolor{green}{5}} = 21 \\[2pt] y_3 &= \frac{105}{\textcolor{blue}{7}} = 15 \end{aligned}$$

Langkah 3. Tentukan nilai $z_i$ yang memenuhi $y_iz_i \equiv 1 \;(\text{mod } m_i)$ untuk $i=1,2,\ldots,r$.

Sebelumnya telah diperoleh nilai $y_1$, $y_2$, dan $y_3$. Sekarang, kita akan menentukan solusi dari $$\begin{aligned} 35z_1 &\equiv 1 \;(\text{mod } \textcolor{red}{3}) \\[2pt] 21z_2 &\equiv 1 \;(\text{mod } \textcolor{green}{5}) \\[2pt] 15z_3 &\equiv 1 \;(\text{mod } \textcolor{blue}{7}) \end{aligned}$$

Kita mulai dengan menentukan solusi dari kongruensi pertama. Untuk memudahkan, kurangi $35$ dengan kelipatan $\textcolor{red}{3}$, misalnya $33$, sehingga diperoleh $$2z_1 \equiv 1 \;(\text{mod } \textcolor{red}{3})$$

Nilai $z_1$ yang memenuhi adalah $2$. Dengan cara serupa, dapat diperoleh $z_2=1$ dan $z_3=1$.

Langkah 4. Tentukan nilai $x$ yang memenuhi sistem kongruensi semula, yaitu $x = a_1y_1z_1+\ldots+a_ry_rz_r$

Pada langkah sebelumnya, kita telah memperoleh nilai $a_i$, $y_i$, dan $z_i$ untuk $i=1,2,3$. Nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= a_1y_1z_1+a_2y_2z_2+a_3y_3z_3 \\[2pt] &= 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \\[2pt] &= 140 + 63 + 30 \\[2pt] &= 233 \end{aligned}$$

Kurangi dengan kelipatan $m=105$ untuk memperoleh bilangan bulat positif terkecil, yaitu $233-2 \cdot 105 = 23$. Secara umum, solusinya adalah $23+ 105k$ dengan $k$ bilangan bulat.

Soal dan Pembahasan

✶ Nomor 1

Tentukan bilangan bulat positif terkecil $x$ sedemikian sehingga $x \equiv 5 \;(\text{mod }7)$, $x \equiv 7 \;(\text{mod }11)$, dan $x \equiv 3 \;(\text{mod }13)$.

Modulus dalam sistem kongruensi tersebut adalah $7$, $11$, dan $13$. Karena ketiganya saling relatif prima, maka berdasarkan Teorema Sisa Cina, sistem tersebut mempunyai solusi.

Nilai $m$ dari sistem tersebut adalah $7 \times 11 \times 13 = 1001$, sehingga $$\begin{aligned} y_1 &= \frac{1001}{7} = \textcolor{teal}{143} \\[2pt] y_2 &= \frac{1001}{11} = \textcolor{teal}{91} \\[2pt] y_3 &= \frac{1001}{13} = \textcolor{teal}{77} \end{aligned}$$

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 143z_1 &\equiv 1 \;(\text{mod }7) \\[2pt] 91z_2 &\equiv 1 \; (\text{mod }11) \\[2pt] 77z_3 &\equiv 1 \; (\text{mod }13) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=5}$, $\textcolor{brown}{z_2=4}$, dan $\textcolor{brown}{z_3=12}$. Dengan demikian, nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 5 \cdot \textcolor{teal}{143} \cdot \textcolor{brown}{5} + 7 \cdot \textcolor{teal}{91} \cdot \textcolor{brown}{4} + 3 \cdot \textcolor{teal}{77} \cdot \textcolor{brown}{12} \\ &= 3575+2548+2772 \\ &= 8895 \end{aligned}$$

Kurangi dengan kelipatan $1001$ untuk memperoleh solusi bulat positif terkecil, yaitu $$x=8895-8 \cdot 1001 = 887$$

Pembahasan
✶ Nomor 2

Tentukan bilangan bulat positif terkecil $x$ sedemikian sehingga $x \equiv 2 \;(\text{mod }3)$, $x \equiv 3 \;(\text{mod }5)$, dan $x \equiv 5 \;(\text{mod }2)$.

Modulus dalam sistem kongruensi tersebut adalah $3$, $5$, dan $2$. Karena ketiganya saling relatif prima, maka berdasarkan Teorema Sisa Cina, sistem tersebut mempunyai solusi.

Nilai $m$ dari sistem tersebut adalah $3 \times 5 \times 2 = 30$, sehingga $$\begin{aligned} y_1 &= \frac{30}{3} = \textcolor{teal}{10} \\[2pt] y_2 &= \frac{30}{5} = \textcolor{teal}{6} \\[2pt] y_3 &= \frac{30}{2} = \textcolor{teal}{15} \end{aligned}$$

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 10z_1 &\equiv 1 \;(\text{mod }3) \\[2pt] 6z_2 &\equiv 1 \; (\text{mod }5) \\[2pt] 15z_3 &\equiv 1 \; (\text{mod }2) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=1}$, $\textcolor{brown}{z_2=1}$, dan $\textcolor{brown}{z_3=1}$. Dengan demikian, nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 2 \cdot \textcolor{teal}{10} \cdot \textcolor{brown}{1} + 3 \cdot \textcolor{teal}{6} \cdot \textcolor{brown}{1} + 5 \cdot \textcolor{teal}{15} \cdot \textcolor{brown}{1} \\ &= 20+18+75 \\ &= 113 \end{aligned}$$

Kurangi dengan kelipatan $30$ untuk memperoleh solusi bulat positif terkecil, yaitu $$x=113-3 \cdot 30 = 23$$

Pembahasan
✶ Nomor 3

Tentukan bilangan bulat positif terkecil $x$ sedemikian sehingga $x \equiv 1 \;(\text{mod }4)$, $x \equiv 0 \;(\text{mod }3)$, dan $x \equiv 5 \;(\text{mod }7)$.

Modulus dalam sistem kongruensi tersebut adalah $4$, $3$, dan $7$. Karena ketiganya saling relatif prima, maka berdasarkan Teorema Sisa Cina, sistem tersebut mempunyai solusi.

Nilai $m$ dari sistem tersebut adalah $4 \times 3 \times 7 = 84$, sehingga $$\begin{aligned} y_1 &= \frac{84}{4} = \textcolor{teal}{21} \\[2pt] y_2 &= \frac{84}{3} = \textcolor{teal}{28} \\[2pt] y_3 &= \frac{84}{7} = \textcolor{teal}{12} \end{aligned}$$

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 21z_1 &\equiv 1 \;(\text{mod }4) \\[2pt] 28z_2 &\equiv 1 \; (\text{mod }3) \\[2pt] 12z_3 &\equiv 1 \; (\text{mod }7) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=1}$, $\textcolor{brown}{z_2=1}$, dan $\textcolor{brown}{z_3=3}$. Dengan demikian, nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 1 \cdot \textcolor{teal}{21} \cdot \textcolor{brown}{1} + 0 \cdot \textcolor{teal}{28} \cdot \textcolor{brown}{1} + 5 \cdot \textcolor{teal}{12} \cdot \textcolor{brown}{3} \\ &= 21+0+180 \\ &= 201 \end{aligned}$$

Kurangi dengan kelipatan $84$ untuk memperoleh solusi bulat positif terkecil, yaitu $$x=201-2 \cdot 84 = 33$$

Pembahasan
✶ Nomor 4

Tentukan bilangan bulat positif terkecil selain $1$ yang bersisa $1$ jika dibagi $3$, $5$, dan $7$.

Misalkan bilangan bulat yang memenuhi adalah $x$, sehingga dapat dibentuk sistem kongruensi linear berikut. $$\left\{ \begin{aligned} x &\equiv 1 \;(\text{mod }3) \\[2pt] x &\equiv 1 \;(\text{mod }5) \\[2pt] x &\equiv 1 \;(\text{mod }7) \end{aligned} \right.$$

Modulus dalam sistem kongruensi tersebut adalah $3$, $5$, dan $7$. Karena ketiganya saling relatif prima, maka Teorema Sisa Cina dapat diterapkan, dengan nilai $m=3 \times 5 \times 7 = 105$.

Perhatikan bahwa $x=1$ memenuhi sistem kongruensi, sehingga secara umum solusinya adalah $$x=1+105k, \quad \text{dengan } k \in \mathbb{Z}$$

Bilangan bulat positif terkecil selain $1$, diperoleh ketika $k=1$ yaitu $$x=1 + 105\cdot 1=106$$

Pembahasan
✶ Nomor 5

Tentukan semua bilangan bulat yang secara berturut-turut bersisa $1$, $2$, dan $3$ ketika dibagi $3$, $4$, dan $5$.

Misalkan bilangan bulat yang memenuhi adalah $x$, sehingga dapat dibentuk sistem kongruensi linear berikut. $$\left\{\begin{aligned} x &\equiv 1 \;(\text{mod }3) \\[2pt] x &\equiv 2 \;(\text{mod }4) \\[2pt] x &\equiv 3 \;(\text{mod }5) \end{aligned}\right.$$

Modulus dalam sistem kongruensi tersebut adalah $3$, $4$, dan $5$. Karena ketiganya saling relatif prima, maka berdasarkan Teorema Sisa Cina, sistem tersebut mempunyai solusi.

Nilai $m$ dari sistem tersebut adalah $3 \times 4 \times 5 = 60$, sehingga $$\begin{aligned} y_1 &= \frac{60}{3} = \textcolor{teal}{20} \\[2pt] y_2 &= \frac{60}{4} = \textcolor{teal}{15} \\[2pt] y_3 &= \frac{60}{5} = \textcolor{teal}{12} \end{aligned}$$

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 20z_1 &\equiv 1 \;(\text{mod }3) \\[2pt] 15z_2 &\equiv 1 \; (\text{mod }4) \\[2pt] 12z_3 &\equiv 1 \; (\text{mod }5) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=2}$, $\textcolor{brown}{z_2=3}$, dan $\textcolor{brown}{z_3=3}$. Dengan demikian, nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 1 \cdot \textcolor{teal}{20} \cdot \textcolor{brown}{2} + 2 \cdot \textcolor{teal}{15} \cdot \textcolor{brown}{3} + 3 \cdot \textcolor{teal}{12} \cdot \textcolor{brown}{3} \\ &= 40+90+108 \\ &= 238 \end{aligned}$$

Kurangi dengan kelipatan $60$ untuk memperoleh solusi positif yang lebih kecil, yaitu $x=238-3 \cdot 60 = 58$. Secara umum, solusinya adalah $x=58+60k$ untuk $k \in \mathbb{Z}$.

Pembahasan
✶ Nomor 6

Banyak siswa dalam suatu kelas kurang dari $36$ siswa. Jika dibagi ke dalam $3$ kelompok, maka akan tersisa $2$ orang. Jika dibagi ke dalam $4$ kelompok, maka akan tersisa $2$ orang. Jika dibagi ke dalam $5$ kelompok, maka akan tersisa $1$ orang. Tentukan banyak siswa dalam kelas tersebut.

Misalkan $x$ menyatakan banyak siswa dalam kelas tersebut, sehingga dapat dibentuk sistem kongruensi linear berikut. $$\left\{\begin{aligned} x &\equiv 2 \;(\text{mod }3) \\[2pt] x &\equiv 2 \;(\text{mod }4) \\[2pt] x &\equiv 1 \;(\text{mod }5) \end{aligned}\right.$$

Modulus dalam sistem kongruensi tersebut saling relatif prima, sehingga mempunyai solusi berdasarkan Teorema Sisa Cina. Nilai $m$ dari sistem tersebut adalah $3 \times 4 \times 5 = 60$, sehingga $$\begin{aligned} y_1 &= \frac{60}{3} = \textcolor{teal}{20} \\[2pt] y_2 &= \frac{60}{4} = \textcolor{teal}{15} \\[2pt] y_3 &= \frac{60}{5} = \textcolor{teal}{12} \end{aligned}$$

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 20z_1 &\equiv 1 \;(\text{mod }3) \\[2pt] 15z_2 &\equiv 1 \; (\text{mod }4) \\[2pt] 12z_3 &\equiv 1 \; (\text{mod }5) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=2}$, $\textcolor{brown}{z_2=3}$, dan $\textcolor{brown}{z_3=3}$, sehingga nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 2 \cdot \textcolor{teal}{20} \cdot \textcolor{brown}{2} + 2 \cdot \textcolor{teal}{15} \cdot \textcolor{brown}{3} + 1 \cdot \textcolor{teal}{12} \cdot \textcolor{brown}{3} \\[2pt] &= 80+90+36 \\[2pt] &= 206 \end{aligned}$$

Karena banyak siswa di kelas tersebut kurang dari $36$, maka nilai $x$ yang diperoleh perlu dikurangi dengan kelipatan $m=60$. $$x=206-3 \cdot 60 = 26$$

Jadi, banyak siswa di kelas tersebut adalah $26$ orang.

Pembahasan
✶ Nomor 7

Tentukan dua digit terakhir dari $49^{49}$.

Misalkan $x$ menyatakan dua digit terakhir dari $49^{49}$ sehingga $$x \equiv 49^{49} \; (\text{mod }100)$$

Perhatikan bahwa $100=4 \times 25$, sehingga kongruensi di atas ekuivalen dengan kongruensi simultan $$\begin{aligned} x &\equiv 49^{49} \; (\text{mod }4) \\[2pt] x &\equiv 49^{49} \; (\text{mod }25) \end{aligned}$$

Kongruensi ini dapat direduksi menjadi $$\begin{aligned} x &\equiv 1 \; (\text{mod }4) \\[2pt] x &\equiv -1 \; (\text{mod }25) \end{aligned}$$

Karena modulusnya relatif prima, maka Teorema Sisa Cina dapat digunakan. Nilai $m$ dari sistem di atas adalah $4 \times 25=100$ dengan $y_1=25$ dan $y_2=4$.

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 25z_1 &\equiv 1 \;(\text{mod }4) \\[2pt] 4z_2 &\equiv 1 \; (\text{mod }25) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=1}$ dan $\textcolor{brown}{z_3=-6}$, sehingga nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 1 \cdot \textcolor{teal}{25} \cdot \textcolor{brown}{1} + (-1) \cdot \textcolor{teal}{4} \cdot \textcolor{brown}{(-6)} \\[2pt] &= 25+24 \\[2pt] &= 49 \end{aligned}$$

Dengan demikian, dua digit terakhir dari $49^{49}$ adalah $49$.

Pembahasan
✶ Nomor 8

Periksa apakah kongruensi $x \equiv 1 \;(\text{mod }10)$ dan $x \equiv 4 \; (\text{mod }15)$ mempunyai solusi bersama. Jika ada, maka tentukan solusinya.

Perhatikan bahwa FPB dari $10$ dan $15$ adalah $5$. Karena modulusnya tidak relatif prima, maka tidak ada jaminan bahwa sistem kongruensi tersebut mempunyai solusi.

Kongruensi pertama ekuivalen dengan kongruensi simultan $$x \equiv 1 \; (\text{mod }2) \quad \text{dan} \quad \textcolor{teal}{x \equiv 1 \; (\text{mod }5)}$$

Sedangkan kongruensi kedua ekuivalen dengan kongruensi simultan $x \equiv 4 \; (\text{mod }3)$ dan $x \equiv 4 \; (\text{mod }5)$ yang dapat direduksi menjadi $$x \equiv 1 \; (\text{mod }3) \quad \text{dan} \quad \textcolor{brown}{x \equiv 4 \; (\text{mod }5)}$$

Perhatikan kongruensi yang mempunyai modulo sama, yaitu $\textcolor{teal}{x \equiv 1 \; (\text{mod }5)}$ dan $\textcolor{brown}{x \equiv 4 \; (\text{mod }5)}$. Tidak ada nilai $x$ yang memenuhi kedua kongruensi ini secara bersamaan. Akibatnya, sistem kongruensi semula tidak mempunyai solusi bersama.

Pembahasan
✶ Nomor 9

Periksa apakah kongruensi $x \equiv 1 \;(\text{mod }6)$ dan $x \equiv 4 \; (\text{mod }15)$ mempunyai solusi bersama. Jika ada, maka tentukan solusinya.

Perhatikan bahwa FPB dari $6$ dan $15$ adalah $3$. Karena modulusnya tidak relatif prima, maka tidak ada jaminan bahwa sistem kongruensi tersebut mempunyai solusi.

Kongruensi pertama ekuivalen dengan kongruensi simultan $$x \equiv 1 \; (\text{mod }2) \quad \text{dan} \quad \textcolor{blue}{x \equiv 1 \; (\text{mod }3)}$$

Sedangkan kongruensi kedua ekuivalen dengan kongruensi simultan $x \equiv 4 \; (\text{mod }3)$ dan $x \equiv 4 \; (\text{mod }5)$ yang dapat direduksi menjadi $$\textcolor{blue}{x \equiv 1 \; (\text{mod }3)} \quad \text{dan} \quad x \equiv 4 \; (\text{mod }5)$$

Terdapat kongruensi yang mempunyai modulo sama. Namun, tidak ada pertentangan antara keduanya, sehingga sistem kongruensi semula mempunyai solusi. Sekarang, sistem kongruensi semula menjadi $$\left\{ \begin{aligned} x \equiv 1 \; (\text{mod }2) \\ x \equiv 1 \; (\text{mod }3) \\ x \equiv 4 \; (\text{mod }5) \end{aligned} \right. \quad \Longrightarrow \quad \left\{ \begin{aligned} x \equiv 1 \; (\text{mod }6) \\ x \equiv 4 \; (\text{mod }5) \end{aligned} \right.$$

Kita akan menggunakan Teorema Sisa Cina untuk menentukan solusinya. Nilai $m$ dari sistem tersebut adalah $6 \times 5=30$, sehingga $$\begin{aligned} y_1 &= \frac{30}{6} = \textcolor{teal}{5} \\[2pt] y_2 &= \frac{30}{5} = \textcolor{teal}{6} \end{aligned}$$

Berikutnya, kita tentukan solusi dari $$\begin{aligned} 5z_1 &\equiv 1 \;(\text{mod }6) \\[2pt] 6z_2 &\equiv 1 \; (\text{mod }5) \end{aligned}$$

Dari kongruensi tersebut diperoleh $\textcolor{brown}{z_1=5}$ dan $\textcolor{brown}{z_2=1}$, sehingga nilai $x$ yang memenuhi adalah $$\begin{aligned} x &= 1 \cdot \textcolor{teal}{5} \cdot \textcolor{brown}{5} + 4 \cdot \textcolor{teal}{6} \cdot \textcolor{brown}{1} \\[2pt] &= 25+24 \\[2pt] &= 49 \end{aligned}$$

Kurangi dengan kelipatan $30$ untuk memperoleh nilai $x$ yang lebih kecil, yaitu $19$. Secara umum, solusinya adalah $19 + 30k$ untuk $k \in \mathbb{Z}$.

Pembahasan
✶ Nomor 10

Periksa apakah kongruensi $5x \equiv 1 \;(\text{mod }6)$ dan $4x \equiv 13 \; (\text{mod }15)$ mempunyai solusi bersama. Jika ada, maka tentukan solusinya.

Kongruensi pertama ekuivalen dengan kongruensi simultan $$5x \equiv 1 \; (\text{mod }2) \quad \text{dan} \quad \textcolor{blue}{5x \equiv 1 \; (\text{mod }3)}$$

Sedangkan kongruensi kedua ekuivalen dengan kongruensi simultan $4x \equiv 13 \; (\text{mod }3)$ dan $4x \equiv 13 \; (\text{mod }5)$ yang dapat direduksi menjadi $$\textcolor{blue}{4x \equiv 1 \; (\text{mod }3)} \quad \text{dan} \quad 4x \equiv 3 \; (\text{mod }5)$$

Terdapat dua kongruensi dengan modulus sama, yaitu $5x \equiv 1 \; (\text{mod }3)$ dan $4x \equiv 1 \; (\text{mod }3)$. Perhatikan bahwa $$\begin{aligned} 5x \equiv 1 \; (\text{mod }3) \quad &\Longrightarrow \quad \textcolor{teal}{x \equiv 2 \; (\text{mod }3)} \\[2pt] 4x \equiv 1 \; (\text{mod }3) \quad &\Longrightarrow \quad \textcolor{brown}{x \equiv 1 \; (\text{mod }3)} \end{aligned}$$

Tidak ada nilai $x$ yang memenuhi $\textcolor{teal}{x \equiv 2 \; (\text{mod }3)}$ dan $\textcolor{brown}{x \equiv 1 \; (\text{mod }3)}$ secara bersamaan. Akibatnya, dua kongruensi semula tidak mempunyai solusi bersama.

Pembahasan