Sistem Kongruensi Linear Archives — Page 2 of 2

Pada zaman dahulu, orang-orang “beruntung” menemui masalah dalam hidupnya terkait sisa hasil bagi. Hal ini terjadi ketika mereka tidak mengetahui banyaknya barang yang dimiliki, tetapi mereka memiliki sejumlah informasi bahwa jika banyaknya barang itu dibagi dengan sejumlah bilangan, maka akan menghasilkan sisa-sisa tertentu. Kebanyakan orang mungkin akan melakukan perhitungan coba-coba, kadang terselesaikan dengan cepat, kadang juga lambat, bahkan sampai tidak ditemukan solusi.

Sebuah kisah tentang seorang nenek pembawa telur berikut mungkin akan menjadi pengantar kita bersama.

Cerita Nenek dan Telurnya

Seorang nenek pergi ke pasar dengan membawa keranjang berisikan beberapa telur. Saat nenek meletakkannya di permukaan tanah, tiba-tiba seorang pemuda datang dan menginjak telur-telur itu secara tidak sengaja hingga pecah semua.

Pemuda itu meminta maaf kepada nenek dan ingin mengganti kerugian nenek. Ia pun bertanya, “Nek, berapa telur yang ada di dalam keranjang Nenek tadi? Saya ingin menggantinya.” Nenek tidak tahu berapa banyak telur di dalam keranjang karena ia tidak pernah menghitungnya. Beruntung, saat di rumah, nenek sempat menyusun telur-telur itu dalam rak telur. Saat nenek menyusun telur pada

3

rak dengan jumlah yang sama, akan ada

2

butir telur yang tersisa. Saat nenek menyusun telur pada

5

rak dengan jumlah yang sama, akan ada

3

butir telur yang tersisa. Saat nenek menyusun telur pada

7

rak dengan jumlah yang sama, ternyata masih ada

2

butir telur tersisa. Pemuda itu pun kebingungan dengan “teka-teki” nenek tersebut.

Sebelum mempelajari teorema sisa Cina, Anda diwajibkan (WAJIB! Tidak ada kompromi) mempelajari materi kongruensi modulo dan invers modulo terlebih dahulu. Salah satu referensi dapat dilihat pada tautan berikut ini.

Baca: Materi, Soal, dan Pembahasan – Kongruensi Modulo

Pada tahun 1809, ketika menganalisis batu yang disebut Pallas, Carl Friedrich Gauss menemukan kembali metode yang digunakan orang Tiongkok sejak dahulu yang sekarang dikenal sebagai teorema sisa Cina. Jauh sebelum itu, sekitar abad ke-6 M, teorema sisa Cina telah digunakan dalam astronomi Cina Kuno untuk mengukur pergerakan planet.

Menurut catatan sejarah, masalah pertama terkait TSC tertulis pada buku karya Jenderal Sun Tzu (544 SM–496 SM) atau juga dikenal sebagai Master Sun. Dalam bukunya yang berjudul “Sun-tzu Suan-ching”, ia menuliskan persoalan berikut.
“Ada barang yang jumlahnya tidak diketahui. Jika kita membaginya dengan $3$ , maka tersisa $2$ . Jika kita membaginya dengan $5$ , maka tersisa $3$ . Jika kita membaginya dengan $7$ , maka tersisa $2$ . Berapa jumlah barang itu?”
Di buku tersebut hanya tertulis soal seperti itu tanpa solusi sehingga menimbulkan ketertarikan untuk menyelesaikannya.

Sekitar abad ke-6 M, suatu algoritma untuk menyelesaikan permasalahan Sun Tzu ditemukan. Algoritma tersebut melibatkan konsep kongruensi modulo dan sekarang kita kenal sebagai teorema sisa Cina (Chinese remainder theorem). Disebut “Cina” karena permasalahan pertama terkait teorema tersebut ditemukan di Negeri Tirai Bambu tersebut.

Teorema Sisa Cina

Misalkan

m_{1}, m_{2}, \dots, m_{r}

adalah bilangan bulat positif sedemikian sehingga

FPB (m_{i}, m_{j}) = 1

untuk

i \neq j

. Sistem kongruensi linear satu variabel

{\begin{cases} x & \equiv a_{1} (mod m_{1}) \\ x & \equiv a_{2} (mod m_{2}) \\ ⋮ \\ x & \equiv a_{r} (mod m_{r}) \end{cases}

mempunyai solusi simultan yang tunggal modulo bilangan bulat.

Bukti

Bentuklah hasil kali $M = m_{1} m_{2} \dots m_{r} .$ Untuk setiap $k = 1, 2, \dots, r,$ misalkan $M_{k} = \frac{M}{m_{k}} = m_{1} m_{2} \dots m_{k - 1} m_{k + 1} \dots m_{r}$ yang sama dengan $M,$ tetapi faktor $m_{k}$ -nya dihilangkan.
Diketahui bahwa $FPB (m_{i}, m_{j}) = 1$ dengan $i \neq j .$ Artinya, $m_{i}$ dan $m_{j}$ relatif prima. Dengan demikian, $FPB (M_{k}, m_{k}) = 1.$
Berdasarkan teorema kongruensi linear, kita dapat menyelesaikan kongruensi $M_{k} x \equiv 1 (mod m_{k}) .$ Sebut saja $x_{k}$ sebagai solusi tunggalnya. Tujuan kita adalah untuk membuktikan bahwa
$\overset{―}{x} \equiv a_{1} M_{1} x_{1} + a_{2} M_{2} x_{2} + \dots + a_{r} M_{r} x_{r} (mod M) .$ adalah solusi simultan dari sistem yang diberikan.
Pertama, amati bahwa $M_{i} \equiv 0 (mod M)$ untuk $i = 1, 2, \dots, r .$ Karena $M | M_{i},$ kita peroleh
$\begin{aligned} \overset{―}{x} & \equiv a_{1} x_{1} + a_{2} x_{2} + \dots + a_{r} x_{r} \\ \equiv a_{k} x_{k} (mod M) . \end{aligned}$ Pilih bilangan bulat $x_{k}$ sedemikian sehingga $M_{k} x_{k} \equiv 1 (mod M) .$
Oleh karena itu, kita dapatkan
$\begin{aligned} \overset{―}{x} & \equiv a_{k} (1) (mod M) \\ \equiv a_{k} (mod M) . \end{aligned}$ Ini menunjukkan bahwa sistem kongruensi tersebut memiliki solusi.
Untuk menunjukkan ketunggalannya, ambil sembarang bilangan bulat $x^{'}$ yang memenuhi sistem kongruensi tersebut sehingga
$\overset{―}{x} \equiv a_{k} \equiv x^{'} (mod M), k = 1, 2, 3, \dots, r$ dan $m_{k} | (\overset{―}{x} - x^{'})$ untuk setiap nilai $k$ . Karena $FPB (m_{i}, m_{j}) = 1$ , diperoleh $m_{1} m_{2} \dots m_{r} | (\overset{―}{x} - x^{'})$ , yang berakibat $\overset{―}{x} \equiv x^{'} (mod n_{k})$ .

[collapse]

Adapun langkah-langkah menyelesaikan persoalan yang melibatkan teorema sisa Cina adalah sebagai berikut.

Nyatakan permasalahan dalam sistem kongruensi linear berikut. ${\begin{cases} x & \equiv a_{1} (mod m_{1}) \\ x & \equiv a_{2} (mod m_{2}) \\ ⋮ \\ x & \equiv a_{r} (mod m_{r}) \end{cases}$
Pastikan bahwa $m_{1}, m_{2}, \dots,$ dan $m_{r}$ semuanya saling relatif prima (memiliki FPB $1$ ). Jika tidak, cobalah sederhanakan kongruensinya dengan menggunakan sifat-sifat kongruensi modulo. Namun, jika sudah dalam bentuk paling sederhana, sistem tersebut tidak dapat diselesaikan dengan menggunakan teorema sisa Cina.
Tuliskan $x_{k} \equiv M_{k}^{- 1} (mod m_{k})$ dan selesaikan invers modulo tersebut.
Nyatakan solusi sistem sebagai
$\begin{aligned} x & \equiv \sum_{i = 1}^{r} (a_{i} M_{i} x_{i}) (mod M) \\ \equiv (a_{1} M_{1} x_{1} + a_{2} M_{2} x_{2} + \dots + a_{r} M_{r} x_{r}) (mod M) . \end{aligned}$

Permasalahan mengenai telur nenek di atas dapat dimodelkan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 2 (mod 3) \\ x & \equiv 3 (mod 5) \\ x & \equiv 2 (mod 7) \end{cases}$ Untuk $M = 3 \times 5 \times 7 = 105$ , diperoleh
$\begin{aligned} M_{1} & = \frac{105}{3} = 35 \\ M_{2} & = \frac{105}{5} = 21 \\ M_{3} & = \frac{105}{7} = 15. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 35^{- 1} (mod 3) \\ \equiv 2 (mod 3) \\ y_{2} & \equiv 21^{- 1} (mod 5) \\ \equiv 1 (mod 5) \\ y_{3} & \equiv 15^{- 1} (mod 7) \\ \equiv 1 (mod 7) . \end{aligned}$ Catatan: Ekspresi tanda pangkat $- 1$ di atas menyatakan invers modulo. Sebaiknya, Anda pelajari terlebih dulu pada tautan di atas jika Anda masih belum memahami bagaimana cara mendapatkan bilangan $2, 1$ , dan $1$ di atas.
Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1) (mod 105) \\ \equiv (140 + 63 + 30) (mod 105) \\ \equiv 233 (mod 105) \\ \equiv 23 (mod 105) . \end{aligned}$ Jadi, kemungkinan banyaknya telur nenek adalah $23$ butir, bisa juga $23 + 105 = 128$ butir, dan seterusnya. Tentu saja, nenek dapat memperkirakan seberapa banyak telurnya, meskipun tidak persis. Ini artinya, permasalahan telur nenek telah terselesaikan.

Baca: Materi, Soal, dan Pembahasan – Algoritma Euclides

Perhatikan dan pahami bagaimana contoh di atas bekerja mengikuti TSC. Sekarang, kita akan membahas soal-soal terkait TSC. Anda bisa mencoba mengerjakan dengan mengikuti alur pengerjaan di atas. Apabila Anda mengalami kebuntuan, silakan cermati pembahasannya.

Today Quote

Mempelajari sejarah adalah salah satu cara kita untuk menghindari kesalahan masa lalu terulang dan mencoba mengulang kesuksesan di masa lalu.

Bagian Pilihan Ganda

Soal Nomor 1

Seorang peternak memiliki sejumlah sapi. Jika ia memasukkan $5$ ekor sapi masing-masing ke dalam sejumlah kandang secukupnya, maka ada $2$ ekor sapi yang tidak masuk kandang. Jika ia memasukkan $6$ ekor sapi masing-masing ke dalam sejumlah kandang secukupnya, maka ada $4$ ekor sapi yang tidak masuk kandang. Banyaknya sapi yang dimiliki peternak tersebut paling sedikit adalah $\dots \cdot$
A. $18$ C. $22$ E. $82$
B. $20$ D. $52$

Pembahasan

Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 2 (mod 5) \\ x & \equiv 4 (mod 6) \end{cases}$ Perhatikan bahwa $5$ dan $6$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 5 \times 6 = 30,$ diperoleh
$\begin{aligned} M_{1} & = \frac{30}{5} = 6 \\ M_{2} & = \frac{30}{6} = 5. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 6^{- 1} (mod 5) \\ \equiv 1 (mod 5) \\ y_{2} & \equiv 5^{- 1} (mod 6) \\ \equiv - 1 (mod 6) \\ \equiv 5 (mod 6) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (2 \cdot 6 \cdot 1 + 4 \cdot 5 \cdot 5) (mod 30) \\ \equiv 112 (mod 30) \\ \equiv 22 (mod 30) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 22 (mod 30) .$
Ini berarti, banyaknya sapi paling sedikit adalah $22$ ekor.
(Jawaban C)

[collapse]

Soal Nomor 2

Misalkan $A$ adalah himpunan solusi dari sistem kongruensi
${\begin{cases} x & \equiv 1 (mod 2) \\ 2 x & \equiv 2 (mod 5) \\ 10 x & \equiv 5 (mod 15) \end{cases}$ Jika $a$ adalah bilangan bulat positif terkecil dari $A$ dan $b$ adalah bilangan bulat positif terbesar dari $A$ dengan $b < 1000$ , maka nilai $a + b = \dots \cdot$
A. $960$ D. $984$
B. $972$ E. $988$
C. $982$

Pembahasan

Diketahui
${\begin{cases} x & \equiv 1 (mod 2) & (\dots 1) \\ 2 x & \equiv 2 (mod 5) & (\dots 2) \\ 10 x & \equiv 5 (mod 15) & (\dots 3) \end{cases}$ Kongruensi $(2)$ dapat disederhanakan menjadi
$x \equiv 1 (mod 5),$ sedangkan Kongruensi $(3)$ dapat disederhanakan menjadi
$\begin{aligned} \frac{10}{5} x & \equiv \frac{5}{5} (mod \frac{15}{5}) \\ 2 x & \equiv 1 (mod 3) \\ x & \equiv 2^{- 1} (mod 3) \\ x & \equiv 2 (mod 3) . \end{aligned}$ Jadi, sistem kongruensi tersebut kita tulis ulang sebagai
${\begin{cases} x & \equiv 1 (mod 2) \\ x & \equiv 1 (mod 5) \\ x & \equiv 2 (mod 3) \end{cases}$ Karena $FPB (2, 5) = 1,$ Kongruensi $(1)$ dan $(2)$ dapat disatukan sehingga diperoleh
${\begin{cases} x & \equiv 1 (mod 10) \\ x & \equiv 2 (mod 3) . \end{cases}$ Perhatikan bahwa $10$ dan $3$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Selanjutnya, kita gunakan teorema sisa Cina.
Untuk $M = 10 \times 3 = 30$ , diperoleh
$\begin{aligned} M_{1} & = \frac{30}{10} = 3 \\ M_{2} & = \frac{30}{3} = 10. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 3^{- 1} (mod 10) \\ \equiv - 3 (mod 10) \\ \equiv 7 (mod 10) \\ y_{2} & \equiv 10^{- 1} (mod 3) \\ \equiv 1 (mod 3) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (1 \cdot 3 \cdot 7 + 2 \cdot 10 \cdot 1) (mod 30) \\ \equiv (21 + 20) (mod 30) \\ \equiv 11 (mod 30) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 11 (mod 30)$ , atau dapat ditulis $x = 30 k + 11$ untuk setiap $k \in Z .$
Nilai $a$ tercapai saat $k = 0$ sehingga $a = 30 (0) + 11 = 11.$
Nilai $b$ tercapai saat $k = 0$ sehingga $a = 30 (32) + 11 = 971.$
Dengan demikian, nilai $a + b = 11 + 971 = 982 .$
(Jawaban C)

[collapse]

Baca: Materi, Soal, dan Pembahasan – Persamaan Diophantine

Soal Nomor 3

Bilangan berikut yang jika dibagi $3, 5$ , dan $7$ berturut-turut memberi sisa $1, 2$ , dan $3$ adalah $\dots \cdot$
A. $42$ C. $62$ E. $82$
B. $52$ D. $72$

Pembahasan

Nyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 1 (mod 3) \\ x & \equiv 2 (mod 5) \\ x & \equiv 3 (mod 7) \end{cases}$ Perhatikan bahwa $3, 5,$ dan $7$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 3 \times 5 \times 7 = 105,$ diperoleh
$\begin{aligned} M_{1} & = \frac{105}{3} = 35 \\ M_{2} & = \frac{105}{5} = 21 \\ M_{3} & = \frac{105}{7} = 15 \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 35^{- 1} (mod 3) \\ \equiv - 1 (mod 3) \\ \equiv 2 (mod 3) \\ y_{2} & \equiv 21^{- 1} (mod 5) \\ \equiv 1 (mod 5) \\ y_{3} & \equiv 15^{- 1} (mod 7) \\ \equiv 1 (mod 7) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (1 \cdot 35 \cdot 2 + 2 \cdot 21 \cdot 1 + 3 \cdot 15 \cdot 1) (mod 105) \\ \equiv (70 + 42 + 45) (mod 105) \\ \equiv 157 (mod 105) \\ \equiv 52 (mod 105) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 52 (mod 105) .$ Ini berarti, semua bilangan bulat $x$ yang memenuhi kongruensi adalah jawabannya. Pada pilihan B, jelas bahwa $52$ memenuhi.
(Jawaban B)

[collapse]

Soal Nomor 4

Misalkan $S$ adalah himpunan bilangan bulat yang jika dibagi $2$ , bersisa 1; jika dibagi $3$ , bersisa $2$ ; dan jika dibagi $4$ , bersisa $3.$ Berapa banyak bilangan bulat pada interval $[0, 10^{4}]$ yang menjadi anggota $S$ ?
A. $433$ D. $833$
B. $633$ E. $834$
C. $832$

Pembahasan

Nyatakan $x \in S$ dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 1 (mod 2) & (\dots 1) \\ x & \equiv 2 (mod 3) & (\dots 2) \\ x & \equiv 3 (mod 4) & (\dots 3) \end{cases}$ Perhatikan bahwa $FPB (2, 4) \neq 1$ sehingga harus dilakukan penyederhanaan lebih dulu.
Dari Kongruensi $(1)$ dan $(3) m$ diperoleh $x = 2 k + 1 = 4 m + 3$ untuk suatu bilangan bulat $k, m .$ Sederhanakan dan kita akan peroleh $k = 2 m + 1.$ Ini menunjukkan bahwa nilai $k$ bergantung pada nilai $m$ . Apa pun nilai bulat $m$ , $k$ juga akan bulat. Oleh karena itu, kedua kongruensi tersebut disederhanakan menurut Kongruensi $(3)$ , yakni $x \equiv 3 (mod 4) .$ Kita peroleh
${\begin{cases} x & \equiv 3 (mod 4) \\ x & \equiv 2 (mod 3) \end{cases}$ Sekarang, ${4, 3}$ relatif prima satu sama lain.
Untuk $M = 4 \times 3 = 12,$ diperoleh
$\begin{aligned} M_{1} & = \frac{12}{4} = 3 \\ M_{2} & = \frac{12}{3} = 4 \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 3^{- 1} (mod 4) \\ \equiv - 1 (mod 4) \\ \equiv 3 (mod 4) \\ y_{2} & \equiv 4^{- 1} (mod 3) \\ \equiv 1 (mod 3. \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (3 \cdot 3 \cdot 3 + 2 \cdot 4 \cdot 1) (mod 12) \\ \equiv (27 + 8) (mod 12) \\ \equiv 35 (mod 12) \\ \equiv 11 (mod 12) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 11 (mod 12) .$ Karena $S \in [0, 10^{4}]$ , haruslah $S = {11, 23, 35, 47, \dots, 9995},$ dengan kardinalitas $n (S) = \frac{9995 - 11}{12} + 1 = 833 .$
(Jawaban D)

[collapse]

Soal Nomor 5

Misalkan $N = 1234567891011 \dots 4344$ adalah bilangan $79$ digit yang didapat dengan cara menuliskan bilangan $1$ sampai $44$ secara berurutan. Berapakah sisa hasil bagi $N$ oleh $45$ ?
A. $1$ C. $9$ E. $44$
B. $4$ D. $18$

Pembahasan

Perhatikan bahwa $45 = 5 \times 9$ . Berdasarkan sifat keterbagian, bilangan habis dibagi $9$ apabila jumlah digit-digit penyusun bilangan tersebut juga habis dibagi $9,$ sedangkan bilangan habis dibagi $5$ jika satuannya $0$ atau $5$ . Dari sini, kita juga sekaligus dapat menentukan sisa hasil baginya jika tidak habis dibagi.
Cek jumlah digit-digit penyusun $N$ , yaitu
$\begin{aligned} 1 + 2 + 3 + \dots + 43 + 44 & = \frac{1 + 44}{2} \times 44^{22} \\ = 45 \times 22. \end{aligned}$ Jelas bahwa hasilnya habis dibagi $9$ karena salah satu faktornya, $45$ , habis dibagi $9.$
Kita peroleh, $N \equiv 0 (mod 9) .$
Selanjutnya, $N$ memiliki satuan $4$ sehingga $N \equiv 4 (mod 5)$ .
Kita peroleh dua kongruensi linear yang membentuk sebuah sistem.
${\begin{cases} N & \equiv 0 (mod 9) \\ N & \equiv 4 (mod 5) \end{cases}$ Gunakan teorema sisa Cina untuk menyelesaikan sistem kongruensi linear di atas.
Perhatikan bahwa $5$ dan $9$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 5 \times 9 = 45,$ diperoleh
$\begin{aligned} M_{1} & tidak perlu dicari \\ M_{2} & = \frac{45}{5} = 9 \end{aligned}$ Catatan: $M_{1}$ dan $y_{1}$ tidak perlu dicari lagi karena hasil kalinya dengan $0$ tetap $0.$
Berikutnya, diperoleh $y_{2} \equiv 9^{- 1} \equiv 4 (mod 5)$ .
Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (0 + 4 \cdot 9 \cdot 4) (mod 45) \\ \equiv (144) (mod 45) \\ \equiv 9 (mod 45) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $N \equiv 9 (mod 45) .$ Ini menunjukkan bahwa $N$ memiliki sisa $9$ jika dibagi $45.$
(Jawaban C)

[collapse]

Baca Juga: Perhitungan Modulo pada ISBN

Soal Nomor 6

Dalam bentuk desimal, bilangan $N = 99999 \dots 999$ terdiri dari $2.020$ buah angka $9.$ Jika $N$ dibagi $2.020,$ maka sisanya $\dots \cdot$
A. $1.818$ D. $2.018$
B. $1.918$ E. $2.019$
C. $1.919$

Pembahasan

Perhatikan bahwa
$\begin{aligned} 99 & = 10^{2} - 1 \\ 999 & = 10^{3} - 1 \\ 9999 & = 10^{4} - 1. \end{aligned}$ Berdasarkan pola yang ada, haruslah
$N = \underset{ada 2.020}{\underset{⏟}{99999 \dots 999}} = 10^{2.020} - 1.$
Misalkan $X = 10^{2.020} .$ Perhatikan bahwa $2.020 = 4 \times 5 \times 101.$ Gunakan teorema sisa Cina dengan menganggap $10^{2.020}$ sebagai salah satu solusi dari sistem kongruensi modulo, yaitu
${\begin{cases} 10^{2.020} & \equiv 0 (mod 4) & (\dots 1) \\ 10^{2020} & \equiv 0 (mod 5) & (\dots 2) \\ 10^{2.020} = 100^{1.010} & \equiv (- 1)^{1.010} (mod 101) \equiv 1 (mod 101) & (\dots 3) . \end{cases}$ Untuk $M = 4 \times 5 \times 101 = 2.020,$ diperoleh
$\begin{aligned} M_{1} & = \frac{2.020}{4} = 505 \\ M_{2} & = \frac{2.020}{5} = 404 \\ M_{3} & = \frac{2.020}{101} = 20. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 505^{- 1} (mod 4) \\ \equiv 1 (mod 4) \\ y_{2} & \equiv 404^{- 1} (mod 5) \\ \equiv 4 (mod 5) \\ y_{3} & \equiv 20^{- 1} (mod 101) \\ \equiv 96 (mod 101) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (0 \cdot 404 \cdot 4 + 0 \cdot 505 \cdot 1 + 1 \cdot 20 \cdot 96) (mod 2.020) \\ \equiv 1920 (mod 2.020) . \end{aligned}$ Jadi, $X = 10^{2.020}$ dibagi oleh $2.020$ bersisa $1920.$ Artinya, $N = 10^{2020} - 1$ dibagi oleh $2.020$ bersisa $1.919 .$
(Jawaban C)

[collapse]

Bagian Uraian

Soal Nomor 1

Carilah solusi dari sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 3 (mod 4) \\ x & \equiv 2 (mod 3) \\ x & \equiv 4 (mod 5) \end{cases}$

Pembahasan

Perhatikan bahwa $3, 4,$ dan $5$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi. Untuk $M = 4 \times 3 \times 5 = 60,$ diperoleh
$\begin{aligned} M_{1} & = \frac{60}{4} = 15 \\ M_{2} & = \frac{60}{3} = 20 \\ M_{3} & = \frac{60}{5} = 12 \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 15^{- 1} (mod 4) \\ \equiv 3 (mod 4) \\ y_{2} & \equiv 20^{- 1} (mod 3) \\ \equiv 2 (mod 3) \\ y_{3} & \equiv 12^{- 1} (mod 5) \\ \equiv 3 (mod 5) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (3 \cdot 15 \cdot 3 + 2 \cdot 20 \cdot 2 + 4 \cdot 12 \cdot 3) (mod 60) \\ \equiv (135 + 80 + 144) (mod 60) \\ \equiv (15 + 20 + 24) (mod 60) \\ \equiv 59 (mod 60) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 59 (mod 60) .$

[collapse]

Soal Nomor 2

Para tentara sedang berbaris di lapangan. Komandan menyusun barisan tentara dalam beberapa formasi.

Jika $4$ tentara disusun per baris, maka tersisa $1$ tentara.
Jika $5$ tentara disusun per baris, maka tersisa $2$ tentara.
Jika $7$ tentara disusun per baris, maka tersisa $4$ tentara.

Paling sedikit berapa banyak tentara di lapangan tersebut (tidak termasuk komandan)?

Pembahasan

Misalkan $x$ menyatakan banyaknya tentara di lapangan. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 1 (mod 4) \\ x & \equiv 2 (mod 5) \\ x & \equiv 4 (mod 7) \end{cases}$ Perhatikan bahwa $4, 5,$ dan $7$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 4 \times 5 \times 7 = 140,$ diperoleh
$\begin{aligned} M_{1} & = \frac{140}{4} = 35 \\ M_{2} & = \frac{140}{5} = 28 \\ M_{3} & = \frac{140}{7} = 20. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 35^{- 1} (mod 4) \\ \equiv - 1 (mod 4) \\ \equiv 3 (mod 4) \\ y_{2} & \equiv 28^{- 1} (mod 5) \\ \equiv 2 (mod 5) \\ y_{3} & \equiv 20^{- 1} (mod 7) \\ \equiv - 1 (mod 7) \\ \equiv 6 (mod 7) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (1 \cdot 35 \cdot 3 + 2 \cdot 28 \cdot 2 + 4 \cdot 20 \cdot 6) (mod 140) \\ \equiv (105 + 112 + 480) (mod 140) \\ \equiv 697 (mod 140) \\ \equiv 137 (mod 140) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 137 (mod 140) .$
Ini berarti, paling sedikit ada $137$ tentara di lapangan tersebut.

[collapse]

Soal Nomor 3

Seorang petani memiliki tiga sistem irigasi berbeda yang dibutuhkan untuk menyiram masing-masing area persawahan. Sistem pertama secara otomatis menyiram area persawahan setiap $3$ hari, sistem kedua $4$ hari, dan sistem ketiga $5$ hari. Petani tersebut juga mengetahui bahwa sistem pertama menyiram area persawahan pada hari ini (hari ke-0), sistem kedua $1$ hari yang lalu (hari ke-1), dan sistem ketiga $4$ hari yang lalu (hari ke-4). Petani tersebut hendak mengetahui hari berikutnya ketika ketiga sistem irigasi tersebut bekerja secara bersamaan.

Pembahasan

Dengan menggunakan teorema sisa Cina, kita dapat menentukan hari ke- $x$ terkecil sehingga ketiga sistem irigasi yang dimaksud bekerja bersamaan. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 0 (mod 3) \\ x & \equiv 1 (mod 4) \\ x & \equiv 4 (mod 5) \end{cases}$ Perhatikan bahwa $3, 4,$ dan $5$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 3 \times 4 \times 5 = 60,$ diperoleh
$\begin{aligned} M_{1} & = \frac{60}{3} = 20 \\ M_{2} & = \frac{60}{4} = 15 \\ M_{3} & = \frac{60}{5} = 12. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 20^{- 1} (mod 3) \\ \equiv 2 (mod 3) \\ y_{2} & \equiv 15^{- 1} (mod 4) \\ \equiv 3 (mod 4) \\ y_{3} & \equiv 12^{- 1} (mod 5) \\ \equiv 3 (mod 5) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (0 \cdot 20 \cdot 2 + 1 \cdot 15 \cdot 3 + 4 \cdot 12 \cdot 3) (mod 60) \\ \equiv (0 + 45 + 144) (mod 60) \\ \equiv 189 (mod 60) \\ \equiv 9 (mod 60) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 9 (mod 60) .$
Ini berarti, hari berikutnya ketika ketiga sistem irigasi tersebut bekerja secara bersamaan adalah hari ke-9.

[collapse]

Soal Nomor 4

Tiga bus, Bus A, Bus B, dan Bus C, berangkat dari terminal keberangkatan pada selang waktu yang berbeda-beda. Bus A berangkat setiap 6 jam, Bus B 7 jam, dan Bus C 11 jam. Diketahui Bus A meninggalkan terminal pada pukul 12.00 hari ini, Bus B pukul 16.00 hari ini, dan Bus C pukul 21.00 hari ini. Manajer terminal hendak mengetahui waktu paling awal saat ketiga bus tersebut berangkat secara bersamaan dari terminal keberangkatan. Selesaikan permasalahan tersebut dengan menggunakan teorema sisa Cina.

Pembahasan

Dengan menggunakan teorema sisa Cina, kita dapat menentukan waktu paling awal $x$ (dalam jam) sehingga ketiga bus tersebut berangkat secara bersamaan dari terminal keberangkatan. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut dengan berpegang pada asumsi bahwa titik awal (0) disepakati pada pukul 12.00.
${\begin{cases} x & \equiv 0 (mod 6) \\ x & \equiv 4 (mod 7) \\ x & \equiv 9 (mod 11) \end{cases}$ Perhatikan bahwa $6, 7,$ dan $11$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 6 \times 7 \times 11 = 462,$ diperoleh
$\begin{aligned} M_{1} & = \frac{462}{6} = 77 \\ M_{2} & = \frac{462}{7} = 66 \\ M_{3} & = \frac{462}{11} = 42. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 77^{- 1} (mod 6) \\ \equiv 5 (mod 6) \\ y_{2} & \equiv 66^{- 1} (mod 7) \\ \equiv 5 (mod 7) \\ y_{3} & \equiv 42^{- 1} (mod 11) \\ \equiv 5 (mod 11) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (0 \cdot 77 \cdot 5 + 4 \cdot 66 \cdot 5 + 9 \cdot 42 \cdot 5) (mod 462) \\ \equiv (0 + 1.320 + 1.890) (mod 462) \\ \equiv 3.210 (mod 462) \\ \equiv 438 (mod 462) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 438 (mod 462) .$
Ini berarti, ketiga bus akan berangkat secara bersamaan dari terminal keberangkatan $438$ jam mendatang terhitung sejak pukul 12.00 hari ini. Dengan kata lain, ketiga bus akan berangkat secara bersamaan dari terminal keberangkatan saat 18 hari + 6 jam mendatang terhitung sejak hari ini.

[collapse]

Soal Nomor 5

Seorang jenderal menghitung banyaknya prajurit yang selamat dari suatu pertempuran dengan mengatur mereka dalam barisan yang terdiri dari sejumlah orang. Sebelumnya, jenderal itu memimpin $1.200$ prajurit dalam perang tersebut.

Jika disusun dalam baris berbanjar $5$ , maka $3$ prajurit tidak memiliki baris.
Jika disusun dalam baris berbanjar $6$ , maka $3$ prajurit tidak memiliki baris.
Jika disusun dalam baris berbanjar $7$ , maka $1$ prajurit tidak memiliki baris.
Jika disusun dalam baris berbanjar $11$ , maka tidak ada prajurit yang tersisa.

Berapa banyak tentara yang selamat?

Pembahasan

Misalkan $x$ menyatakan banyaknya tentara yang selamat (dan ikut berbaris). Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 3 (mod 5) \\ x & \equiv 3 (mod 6) \\ x & \equiv 1 (mod 7) \\ x & \equiv 0 (mod 11) \end{cases}$ Perhatikan bahwa $5, 6, 7,$ dan $11$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 5 \times 6 \times 7 \times 11 = 2.310,$ diperoleh
$\begin{aligned} M_{1} & = \frac{2.310}{5} = 462 \\ M_{2} & = \frac{2.310}{6} = 385 \\ M_{3} & = \frac{2.310}{7} = 330 \\ M_{4} & tidak perlu dicari . \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv 462^{- 1} (mod 5) \\ \equiv - 2 (mod 5) \\ \equiv 3 (mod 5) \\ y_{2} & \equiv 385^{- 1} (mod 6) \\ \equiv 1 (mod 6) \\ y_{3} & \equiv 330^{- 1} (mod 7) \\ \equiv 1 (mod 7) . \end{aligned}$ Catatan: Perhatikan bahwa kita tidak perlu menghitung $M_{4}$ dan $y_{4}$ karena $a_{4}$ bernilai $0$ sehingga hasil perkaliannya nanti pasti $0.$
Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (3 \cdot 462 \cdot 3 + 3 \cdot 385 \cdot 1 + 1 \cdot 330 \cdot 1 + 0) (mod 2.310) \\ \equiv (4.158 + 1.155 + 330) (mod 2.310) \\ \equiv 5.643 (mod 2.310) \\ \equiv 1.023 (mod 2.310) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 1.023 (mod 2.310) .$
Karena $1.023 < 1.200$ (jumlah tentara semula), jumlah tentara yang selamat sebanyak $1.023$ orang.

[collapse]

Soal Nomor 6

Aku adalah bilangan terkecil yang jika dibagi $5,$ bersisa $4$ ; jika dibagi $6,$ bersisa $3$ ; jika dibagi $11$ , bersisa $9$ ; dan jika dibagi $17$ , bersisa $2.$
Bilangan berapakah aku?

Pembahasan

Misalkan $x$ menyatakan bilangan “aku”. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 4 (mod 5) \\ x & \equiv 3 (mod 6) \\ x & \equiv 9 (mod 11) \\ x & \equiv 2 (mod 17) \end{cases}$ Perhatikan bahwa $5, 6, 11,$ dan $17$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 5 \times 6 \times 11 \times 17 = 5.610,$ diperoleh
$\begin{aligned} M_{1} & = \frac{5.610}{5} = 1.122 \\ M_{2} & = \frac{5.610}{6} = 935 \\ M_{3} & = \frac{5.610}{11} = 510 \\ M_{4} & = \frac{5.610}{17} = 330. \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv {1.122}^{- 1} (mod 5) \\ \equiv - 2 (mod 5) \\ \equiv 3 (mod 5) \\ y_{2} & \equiv 935^{- 1} (mod 6) \\ \equiv - 1 (mod 6) \\ \equiv 5 (mod 6) \\ y_{3} & \equiv 510^{- 1} (mod 11) \\ \equiv 3 (mod 11) \\ y_{4} & \equiv 330^{- 1} (mod 17) \\ \equiv 5 (mod 17) . \end{aligned}$ Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (4 \cdot 1.122 \cdot 3 + 3 \cdot 935 \cdot 5 + 9 \cdot 510 \cdot 3 + 2 \cdot 330 \cdot 5) (mod 5.610) \\ \equiv (13.464 + 14.025 + 22.950 + 2.300) (mod 5.610) \\ \equiv 44.559 (mod 5.610) \\ \equiv 5.289 (mod 5.610) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 5.289 (mod 5.610)$ . Karena aku adalah bilangan terkecil yang memenuhi kriteria di atas, aku adalah bilangan $5.289 .$

[collapse]

Soal Nomor 7

Di dalam akuarium besar, terdapat sejumlah ikan cupang. Jika ikan cupang tersebut dikeluarkan dengan pengambilan sebanyak $2, 3, 5,$ atau $7$ ekor setiap waktu, akan ada $1$ ekor ikan cupang yang tersisa. Namun, jika pengambilan ikan dilakukan sebanyak $11$ ekor setiap waktu, tidak ada ikan cupang yang tersisa di dalam akuarium tersebut. Berapa ekor ikan cupang di dalam akuarium tersebut jika diketahui banyaknya ikan tidak melebihi $2.500$ ekor?

Pembahasan

Misalkan $x$ menyatakan banyaknya ikan cupang di dalam akuarium. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
${\begin{cases} x & \equiv 1 (mod 2) \\ x & \equiv 1 (mod 3) \\ x & \equiv 1 (mod 5) \\ x & \equiv 1 (mod 7) \\ x & \equiv 0 (mod 11) \end{cases}$ Perhatikan bahwa $2, 3, 5, 7,$ dan $11$ adalah bilangan-bilangan yang saling relatif prima sehingga sistem tersebut memiliki solusi.
Untuk $M = 2 \times 3 \times 5 \times 7 \times 11 = 2.310,$ diperoleh
$\begin{aligned} M_{1} & = \frac{2.310}{2} = 1.155 \\ M_{2} & = \frac{2.310}{3} = 770 \\ M_{3} & = \frac{2.310}{5} = 462 \\ M_{4} & = \frac{2.310}{7} = 330 \\ M_{5} & tidak perlu dicari . \end{aligned}$ Dengan demikian, diperoleh
$\begin{aligned} y_{1} & \equiv {1.155}^{- 1} (mod 2) \\ \equiv 1 (mod 2) \\ y_{2} & \equiv 770^{- 1} (mod 3) \\ \equiv 2 (mod 3) \\ y_{3} & \equiv 462^{- 1} (mod 5) \\ \equiv 3 (mod 5) \\ y_{4} & \equiv 330^{- 1} (mod 5) \\ \equiv 1 (mod 7) . \end{aligned}$ Catatan: Perhatikan bahwa kita tidak perlu menghitung $M_{5}$ dan $y_{5}$ karena $a_{5}$ bernilai $0$ sehingga hasil perkaliannya nanti pasti $0.$
Berdasarkan teorema sisa Cina, kita dapatkan solusi
$\begin{aligned} x & \equiv (1 \cdot 1.155 \cdot 1 + 1 \cdot 770 \cdot 2 + 1 \cdot 462 \cdot 3 + 1 \cdot 330 \cdot 1 + 0) (mod 2.310) \\ \equiv (4.411) (mod 2.310) \\ \equiv 2.101 (mod 2.310) . \end{aligned}$ Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 2.101 (mod 2.310) .$
Karena diketahui bahwa banyaknya ikan tidak melebihi $2.500$ ekor, satu-satunya nilai $x$ yang memenuhi adalah $2.101 .$ Artinya, banyaknya ikan cupang di dalam akuarium tersebut adalah $2.101$ ekor.

[collapse]

Tag: Sistem Kongruensi Linear

Materi, Soal, dan Pembahasan – Teorema Sisa Cina

Cerita Nenek dan Telurnya

Teorema Sisa Cina

Today Quote

Soal Nomor 1

Soal Nomor 2

Soal Nomor 3

Soal Nomor 4

Soal Nomor 5

Soal Nomor 6

Soal Nomor 1

Soal Nomor 2

Soal Nomor 3

Soal Nomor 4

Soal Nomor 5

Soal Nomor 6

Soal Nomor 7