Anda diharapkan telah mempelajari cara menentukan solusi dari sebuah kongruensi linear. Sekarang, bagaimana kalau solusi tersebut harus berlaku untuk sejumlah kongruensi linear? Hal ini analog dengan momen ketika Anda dapat menyelesaikan sebuah persamaan linear, kemudian belajar menyelesaikan sistem persamaan linear dengan berbagai cara, termasuk dengan menggunakan aturan Cramer dan eliminasi Gauss (Gauss-Jordan).
Dengan cara klasik, Anda akan mempelajari cara mencari solusi dari sistem kongruensi linear pada bagian ini, termasuk membuktikan sebuah teorema yang menyatakan bentuk umum dari solusi tersebut. Namun, ada sejumlah batasan yang dikaji dalam artikel ini, yaitu sebagai berikut.
- Sistem kongruensi linear yang Anda punya terdiri dari 2 kongruensi dan 2 variabel.
- Modulus dari setiap kongruensi bernilai sama.
Sebelum lanjut, Anda perlu mengingat kembali definisi dan teorema berikut. Sebagai informasi, notasi $(a, b)$ menyatakan faktor persekutuan terbesar (FPB) dari bilangan bulat $a$ dan $b.$
Definisi: Kongruen
Definisi: Invers Modular
Teorema 1: Operasi Aritmetika dalam Kongruensi Modulo
$$\begin{aligned} a + c & \equiv b + d~(\text{mod}~m), \\ a-c & \equiv b-d~(\text{mod}~m), \\ ac & \equiv bd~(\text{mod}~m). \end{aligned}$$
Teorema 2: Solusi Takkongruen Modulo $m$
Mari awali pembahasan dengan contoh-contoh berikut.
Contoh 1
$$\begin{aligned} x + 2y & \equiv 1~(\text{mod}~5) \\ 2x + y & \equiv 1~(\text{mod}~5) \end{aligned}$$
Pembahasan:
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} x + 2y & \equiv 1~(\text{mod}~5) && (1) \\ 2x + y & \equiv 1~(\text{mod}~5) && (2) \end{aligned}$$Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(2)$ dengan $2,$ kemudian kurangi Kongruensi $(2)$ dengan $(1)$ sehingga didapat
$$3x \equiv 1~(\text{mod}~5).$$Karena $2$ adalah invers dari $3~(\text{mod}~5),$ kalikan kedua ruas kongruensi $3x \equiv 1~(\text{mod}~5)$ dengan $2$ sehingga didapat
$$2(3x) \equiv 1(2)~(\text{mod}~5)$$yang berarti
$$x \equiv 2~(\text{mod}~5).$$Substitusi nilai $x$ ini pada Kongruensi $(1)$ akan menghasilkan
$$\begin{aligned} 2 + 2y & \equiv 1~(\text{mod}~5) \\ 2y & \equiv 4~(\text{mod}~5) \\ y & \equiv 2~(\text{mod}~5). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah semua pasangan $(x, y)$ yang memenuhi $x \equiv y \equiv 2~(\text{mod}~5).$
Contoh 2
$$\begin{aligned} 4x + y & \equiv 5~(\text{mod}~7) \\ x + 2y & \equiv 4~(\text{mod}~7) \end{aligned}$$
Pembahasan:
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 4x+y & \equiv 5~(\text{mod}~7) && (1) \\ x+2y & \equiv 4~(\text{mod}~7) && (2) \end{aligned}$$Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(1)$ dengan $2,$ kemudian kurangi Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$7x \equiv 6~(\text{mod}~7).$$Namun, $7x \equiv 0~(\text{mod}~7)$ sehingga kita peroleh $0 \equiv 6~(\text{mod}~7).$ Pernyataan tersebut tentu saja bernilai salah. Dari sini, kita langsung dapat menyimpulkan bahwa sistem tidak memiliki solusi.
Contoh 3
$$\begin{aligned} 4x + y & \equiv 2~(\text{mod}~5) \\ 2x + 3y & \equiv 1~(\text{mod}~5) \end{aligned}$$
Pembahasan:
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 4x + y & \equiv 2~(\text{mod}~5) && (1) \\ 2x + 3y & \equiv 1~(\text{mod}~5). && (2) \end{aligned}$$Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(1)$ dengan $3,$ kemudian kurangi Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$10x \equiv 0~(\text{mod}~5).$$Dari $10x \equiv 0~(\text{mod}~5),$ diperoleh $x \equiv 0, 1, 2, 3, 4~(\text{mod}~5).$ Substitusi nilai $x$ tersebut pada Kongruensi (1) akan berturut-turut menghasilkan $y \equiv 2, 3, 4, 0, 1~(\text{mod}~5).$ Jadi, sistem kongruensi linear tersebut memiliki $5$ solusi takkongruen modulo $5.$
Dengan menggunakan ilustrasi yang ditunjukkan pada contoh-contoh di atas, teorema berikut dapat dibuktikan.
Teorema: Solusi Sistem Kongruensi Linear
$$\begin{aligned} ax + by & \equiv e~(\text{mod}~m) \\ cx + dy & \equiv f~(\text{mod}~m) \end{aligned}$$memiliki solusi tunggal modulo $m$ yang dinyatakan oleh
$$\begin{aligned} x & \equiv \overline{\Delta}(de-bf)(\text{mod}~m) \\ y & \equiv \overline{\Delta}(af-ce)(\text{mod}~m) \end{aligned}$$dengan $\overline{\Delta}$ adalah invers dari $\Delta$ modulo $m.$
Misalkan $a, b, c, d, e, f,$ dan $m$ merupakan bilangan bulat dengan $m > 0$ dan $(\Delta, m) = 1$ dengan $\Delta = ad-bc.$ Pandang sistem kongruensi
$$\begin{aligned} ax + by & \equiv e~(\text{mod}~m) && (1) \\ cx + dy & \equiv f~(\text{mod}~m) && (2) \end{aligned}$$dengan $\overline{\Delta}$ adalah invers dari $\Delta$ modulo $m.$
Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(1)$ dengan $d$ dan Kongruensi $(2)$ dengan $b$ untuk memperoleh
$$\begin{aligned} adx + bdy & \equiv de~(\text{mod}~m) && (3) \\ bcx + bdy & \equiv bf~(\text{mod}~m). && (4) \end{aligned}$$Kemudian, kurangi Kongruensi $(3)$ dengan Kongruensi $(4)$ untuk menghasilkan
$$(ad-bc)x \equiv de-bf~(\text{mod}~m).$$Karena $\Delta = ad-bc,$ dapat ditulis
$$\color{red}{\Delta x \equiv de-bf~(\text{mod}~m)}.$$Berikutnya, kalikan kedua ruas dengan $\overline{\Delta},$ yaitu invers dari $\Delta$ modulo $m,$ agar didapat
$$x \equiv \overline{\Delta}(de-bf)~(\text{mod}~m).$$Dengan cara yang serupa, akan diperoleh
$$y \equiv \overline{\Delta}(af-ce)~(\text{mod}~m).$$Jadi, jika $(x, y)$ adalah solusi dari sistem kongruensi linear tersebut, maka
$$x \equiv \overline{\Delta}(de-bf)~(\text{mod}~m),~~~~~~y \equiv \overline{\Delta}(af-ce)~(\text{mod}~m).$$Setiap pasangan bilangan bulat $(x, y)$ dengan $x \equiv \overline{\Delta}(de-bf)~(\text{mod}~m)$ dan $y \equiv \overline{\Delta}(af-ce)~(\text{mod}~m)$ merupakan solusi sistem kongruensi linear tersebut karena
$$\begin{aligned} ax + by & \equiv a(\overline{\Delta}(de-bf)) + b(\overline{\Delta}(af-ce)) \\ & \equiv \overline{\Delta}(ade-abf + abf-bce) \\ & \equiv \overline{\Delta}(ad-bc)e \\ & \equiv \overline{\Delta}\Delta e \equiv e~(\text{mod}~m) \end{aligned}$$dan
$$\begin{aligned} cx + dy & \equiv c(\overline{\Delta}(de-bf)) + d(\overline{\Delta}(af-ce)) \\ & \equiv \overline{\Delta}(cde-bcf+adf-cde) \\ & \equiv \overline{\Delta}(ad-bc)f \\ & \equiv \overline{\Delta}\Delta f \equiv f~(\text{mod}~m). \end{aligned}$$ $\blacksquare$
Pertanyaan eksploratif:
Misalkan $a, b, c, d, e, f,$ dan $m$ merupakan bilangan bulat dengan $m > 0.$ Kapan sistem kongruensi linear
$$\begin{aligned} ax + by & \equiv e~(\text{mod}~m) \\ cx + dy & \equiv f~(\text{mod}~m) \end{aligned}$$tidak memiliki solusi atau banyak solusi?
Karena kedua kongruensi dalam sistem tersebut ekuivalen dengan $\Delta x \equiv de-bf~(\text{mod}~m),$ berdasarkan Teorema $2,$ diperoleh kesimpulan sebagai berikut.
- Sistem tidak memiliki solusi ketika $(\Delta, m) \nmid (de-bf).$
- Sistem memiliki $(\Delta, m)$ solusi takkongruen modulo $m$ ketika $(\Delta, m) \mid (de-bf).$
Jika Anda ingin mencari soal latihan yang lebih banyak, Anda dapat mengakses ke folder soal mathcyber1997.com dengan mendaftar di . Folder soal tersebut tidak hanya berisi soal UTBK-SNBT, melainkan juga soal persiapan CPNS-PPPK, soal psikotes, soal TPA, soal ujian masuk perguruan tinggi, soal kompetensi matematika, dan masih banyak lagi.
Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber yang digunakan di antaranya adalah buku “Elementary Number Theory & Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.
$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Kongruensi Modulo} & \text{Congruence Modulo} \\ 2. & \text{Sistem Kongruensi Linear} & \text{System of Linear Congruences} \\ 3. & \text{Solusi Takkongruen} & \text{Incongruent Solution} \\ \hline \end{array}$$
Today Quote
Bagian Pilihan Ganda
Soal Nomor 1
Tentukan semua pasangan bilangan bulat $(x, y)$ yang memenuhi sistem kongruensi linear berikut.
$$\begin{aligned} x + 3y & \equiv 1~(\text{mod}~5) \\ 3x + 4y & \equiv 2~(\text{mod}~5) \end{aligned}$$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} x + 3y & \equiv 1~(\text{mod}~5) && (1) \\ 3x + 4y & \equiv 2~(\text{mod}~5) && (2) \end{aligned}$$Untuk mengeliminasi variabel $x,$ kalikan Kongruensi $(1)$ dengan $3,$ kemudian kurangi Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$5y \equiv 1~(\text{mod}~5).$$Namun, $5y \equiv 0~(\text{mod}~5)$ sehingga kita peroleh $0 \equiv 1~(\text{mod}~5).$ Pernyataan tersebut tentu saja bernilai salah. Dari sini, kita langsung dapat menyimpulkan bahwa sistem tidak memiliki solusi.
Soal Nomor 2
Tentukan semua pasangan bilangan bulat $(x, y)$ yang memenuhi sistem kongruensi linear berikut.
$$\begin{aligned} 7x + 2y & \equiv 3~(\text{mod}~6) \\ x-4y & \equiv 2~(\text{mod}~6) \end{aligned}$$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 7x + 2y & \equiv 3~(\text{mod}~6) && (1) \\ x-4y & \equiv 2~(\text{mod}~6) && (2) \end{aligned}$$Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(1)$ dengan $3,$ kemudian jumlahkan Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$15x \equiv 2~(\text{mod}~6).$$Perhatikan bahwa $(15, 6) = 3 \neq 1$ sehingga kongruensi $15x \equiv 2~(\text{mod}~6)$ tidak memiliki solusi. Dari sini, dapat disimpulkan bahwa sistem kongruensi linear semula juga tidak memiliki solusi.
Soal Nomor 3
Tentukan semua pasangan bilangan bulat $(x, y)$ yang memenuhi sistem kongruensi linear berikut.
$$\begin{aligned} 4x + 5y & \equiv 3~(\text{mod}~7) \\ 3x-4y & \equiv 2~(\text{mod}~7) \end{aligned}$$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 4x + 5y & \equiv 3~(\text{mod}~7) && (1) \\ 3x-4y & \equiv 2~(\text{mod}~7) && (2) \end{aligned}$$Untuk mengeliminasi variabel $x,$ kalikan Kongruensi $(1)$ dengan $3$ dan kalikan Kongruensi $(2)$ dengan $4,$ kemudian kurangi Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$31y \equiv 1~(\text{mod}~7).$$Karena invers dari $31~(\text{mod}~7)$ adalah $5,$ perkalian dengan $5$ pada kedua ruas kongruensi tersebut akan menghasilkan
$$y \equiv 5~(\text{mod}~7).$$Substitusi pada Kongruensi $(2)$ akan menghasilkan
$$\begin{aligned} 3x -4(5) & \equiv 2~(\text{mod}~7) \\ 3x & \equiv 1~(\text{mod}~7). \end{aligned}$$Karena invers dari $3~(\text{mod}~7)$ adalah $5,$ perkalian dengan $5$ pada kedua ruas kongruensi tersebut akan menghasilkan $$x \equiv 5~(\text{mod}~7).$$Jadi, solusi dari sistem kongruensi linear tersebut adalah semua pasangan $(x, y)$ yang memenuhi $x \equiv y \equiv 5~(\text{mod}~7).$
Soal Nomor 4
Tentukan semua pasangan bilangan bulat $(x, y)$ yang memenuhi sistem kongruensi linear berikut.
$$\begin{aligned} 4x-y & \equiv 3~(\text{mod}~11) \\ 5x+4y & \equiv 7~(\text{mod}~11) \end{aligned}$$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 4x-y & \equiv 3~(\text{mod}~11) && (1) \\ 5x+4y & \equiv 7~(\text{mod}~11) && (2) \end{aligned}$$Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(1)$ dengan $4,$ kemudian jumlahkan Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$21x \equiv 8~(\text{mod}~11).$$Karena invers dari $21~(\text{mod}~11)$ adalah $-1,$ perkalian dengan $-1$ pada kedua ruas kongruensi tersebut akan menghasilkan
$$x \equiv -8 \equiv 3~(\text{mod}~11).$$Substitusi pada Kongruensi $(1)$ akan menghasilkan
$$\begin{aligned} 4(3) -y & \equiv 3~(\text{mod}~11) \\ -y & \equiv -9~(\text{mod}~11) \\ y & \equiv 9~(\text{mod}~11). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah semua pasangan $(x, y)$ yang memenuhi $x \equiv 3~(\text{mod}~11)$ dan $y \equiv 9~(\text{mod}~11).$
Soal Nomor 5
Tentukan semua pasangan bilangan bulat $(x, y)$ yang memenuhi sistem kongruensi linear berikut.
$$\begin{aligned} 7x+3y & \equiv 10~(\text{mod}~16) \\ 2x+5y & \equiv 9~(\text{mod}~16) \end{aligned}$$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 7x+3y & \equiv 10~(\text{mod}~16) && (1) \\ 2x+5y & \equiv 9~(\text{mod}~16) && (2) \end{aligned}$$Untuk mengeliminasi variabel $y,$ kalikan Kongruensi $(1)$ dengan $5$ dan kalikan Kongruensi $(2)$ dengan $3,$ kemudian kurangi Kongruensi $(1)$ dengan $(2)$ sehingga didapat
$$29x \equiv 7~(\text{mod}~16).$$Karena invers dari $29~(\text{mod}~16)$ adalah $5,$ perkalian dengan $5$ pada kedua ruas kongruensi tersebut akan menghasilkan
$$x \equiv 35 \equiv 3~(\text{mod}~16).$$Substitusi pada Kongruensi $(1)$ akan menghasilkan
$$\begin{aligned} 7(3) + 3y & \equiv 10~(\text{mod}~16) \\ 3y & \equiv 5~(\text{mod}~16) \\ y & \equiv 7~(\text{mod}~16) \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah semua pasangan $(x, y)$ yang memenuhi $x \equiv 3~(\text{mod}~16)$ dan $y \equiv 7~(\text{mod}~16).$
Soal Nomor 6
Berapa banyak bilangan bulat $k$ sehingga sistem kongruensi linear berikut tidak memiliki solusi?
$$\begin{aligned} kx-y & \equiv 1~(\text{mod}~3) \\ 3x+y & \equiv 2~(\text{mod}~3) \end{aligned}$$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} kx-y & \equiv 1~(\text{mod}~3) && (1) \\ 3x+y & \equiv 2~(\text{mod}~3) && (2) \end{aligned}$$Perhatikan bahwa $$\Delta = ad-bc = (k)(1)-(-1)(3) = k+3$$ dan $$de-bf=(1)(1)-(-1)(2) = 3.$$Agar sistem kongruensi linear tersebut tidak memiliki solusi, haruslah $(\Delta, m) \nmid de-bf,$ atau $(k+3, 3) \nmid 3.$ Namun, $(k+3, 3)$ hanya memiliki dua kemungkinan nilai, yaitu $(k+3, 3) = 3$ saat $k$ merupakan bilangan bulat kelipatan $3$ dan $(k+3, 3) = 1$ saat $k$ bukan bilangan bulat kelipatan $3.$ Dengan kata lain, berapa pun nilai $k,$ $(k+3, 3)$ selalu membagi $3$ karena $1 \mid 3$ dan $3 \mid 3.$ Hal ini menunjukkan bahwa tidak ada satu pun bilangan bulat $k$ yang membuat sistem kongruensi linear tersebut tidak memiliki solusi. Artinya, banyak bilangan bulat $k$ yang memenuhi adalah $\boxed{0}.$
Soal Nomor 7
Misalkan $k$ merupakan bilangan bulat positif terkecil sehingga sistem kongruensi linear
$$\begin{aligned} 3x + 4y & \equiv k~(\text{mod}~11) \\ 2x-y & \equiv 2~(\text{mod}~11) \end{aligned}$$memiliki $11$ solusi takkongruen modulo $11.$ Tentukan nilai $k.$
Diketahui sistem kongruensi linear berikut.
$$\begin{aligned} 3x + 4y & \equiv k~(\text{mod}~11) && (1) \\ 2x-y & \equiv 2~(\text{mod}~11) && (2) \end{aligned}$$Perhatikan bahwa $$\Delta = ad-bc = (3)(-1)-(4)(2) = -11$$ dan $$de-bf=(-1)k-(4)(2)=-k-8.$$Selain itu, $(\Delta, m) = (-11, 11) = 11.$ Agar sistem kongruensi linear tersebut memiliki $11$ solusi takkongruen modulo $11,$ haruslah $(\Delta, m) \mid de-bf,$ atau $11 \mid -k-8.$ Karena $k$ merupakan bilangan bulat positif terkecil, keterbagian tersebut akan terpenuhi saat $k = 3.$ Jadi, nilai $k$ yang dimaksud adalah $\boxed{3}.$
Soal Nomor 8
Buktikan bahwa setiap bilangan bulat $k$ membuat sistem kongruensi linear
$$\begin{aligned} 4x + ky & \equiv 2~(\text{mod}~7) \\ 3x-(k+2)y & \equiv 5~(\text{mod}~7) \end{aligned}$$memiliki tepat satu solusi kongruen modulo $7.$
Ambil sembarang bilangan bulat $k$ yang memenuhi sistem kongruensi linear berikut.
$$\begin{aligned} 4x + ky & \equiv 2~(\text{mod}~7) && (1) \\ 3x-(k+2)y & \equiv 5~(\text{mod}~7) && (2) \end{aligned}$$Perhatikan bahwa $$\Delta = ad-bc = 4(-k-2)-(k)(3) = -7k-8$$ dan $$de-bf=(-k-2)(2)-(k)(5) = -7k-4.$$Selain itu, $(\Delta, m) = (-7k-8, -7) = 1$ karena $-7k-8$ tidak habis dibagi $7$ untuk setiap bilangan bulat $k.$ Agar sistem kongruensi linear tersebut memiliki tepat satu solusi kongruen modulo $7,$ haruslah $(\Delta, m) \mid de-bf,$ atau $1 \mid -7k-4.$ Untuk setiap bilangan bulat $k,$ keterbagian tersebut pasti terpenuhi. Dengan menggunakan Teorema 2, terbukti bahwa setiap bilangan bulat $k$ membuat sistem kongruensi linear
$$\begin{aligned} 4x + ky & \equiv 2~(\text{mod}~7) \\ 3x-(k+2)y & \equiv 5~(\text{mod}~7) \end{aligned}$$memiliki tepat satu solusi kongruen modulo $7.$ $\blacksquare$