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
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
$$\begin{cases} x & \equiv a_1~(\text{mod}~m_1) \\ x & \equiv a_2~(\text{mod}~m_2) \\ & \vdots \\ x & \equiv a_r~(\text{mod}~m_r) \end{cases}$$mempunyai solusi simultan yang tunggal modulo bilangan bulat.
Bentuklah hasil kali $M = m_1m_2\cdots m_r.$ Untuk setiap $k = 1, 2, \cdots, r,$ misalkan $$M_k = \dfrac{M}{m_k} = m_1m_2\cdots m_{k-1}m_{k+1}\cdots m_r$$yang sama dengan $M,$ tetapi faktor $m_k$-nya dihilangkan.
Diketahui bahwa $\text{FPB}(m_i, m_j) = 1$ dengan $i \neq j.$ Artinya, $m_i$ dan $m_j$ relatif prima. Dengan demikian, $\text{FPB}(M_k, m_k) = 1.$
Berdasarkan teorema kongruensi linear, kita dapat menyelesaikan kongruensi $M_kx \equiv 1~(\text{mod}~m_k).$ Sebut saja $x_k$ sebagai solusi tunggalnya. Tujuan kita adalah untuk membuktikan bahwa
$$\overline{x}\equiv a_1M_1x_1 + a_2M_2x_2 + \cdots + a_rM_rx_r~(\text{mod}~M).$$adalah solusi simultan dari sistem yang diberikan.
Pertama, amati bahwa $M_i \equiv 0~(\text{mod}~M)$ untuk $i = 1, 2, \cdots, r.$ Karena $M~|~M_i,$ kita peroleh
$$\begin{aligned} \overline{x} & \equiv a_1x_1 + a_2x_2 + \cdots + a_rx_r \\ & \equiv a_kx_k~(\text{mod}~M). \end{aligned}$$Pilih bilangan bulat $x_k$ sedemikian sehingga $M_kx_k \equiv 1~(\text{mod}~M).$
Oleh karena itu, kita dapatkan
$$\begin{aligned} \overline{x} & \equiv a_k(1)~(\text{mod}~M) \\ & \equiv a_k~(\text{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
$$\overline{x} \equiv a_k \equiv x’~(\text{mod}~M), k = 1,2,3,\cdots,r$$dan $m_k~|~(\overline{x}-x’)$ untuk setiap nilai $k$. Karena $\text{FPB}(m_i, m_j) = 1$, diperoleh $m_1m_2\cdots m_r~|~(\overline{x}-x’)$, yang berakibat $\overline{x} \equiv x’~(\text{mod}~n_k)$. $\blacksquare$
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~(\text{mod}~m_1) \\ x & \equiv a_2~(\text{mod}~m_2) \\ & \vdots \\ x & \equiv a_r~(\text{mod}~m_r) \end{cases}$$
- Pastikan bahwa $m_1, m_2, \cdots,$ 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}~(\text{mod}~m_k)$ dan selesaikan invers modulo tersebut.
- Nyatakan solusi sistem sebagai
$$\begin{aligned} x & \equiv \displaystyle \sum_{i=1}^r (a_iM_ix_i)~(\text{mod}~M) \\ & \equiv (a_1M_1x_1 + a_2M_2x_2 + \cdots + a_rM_rx_r)~(\text{mod}~M). \end{aligned}$$
Permasalahan mengenai telur nenek di atas dapat dimodelkan dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 2~(\text{mod}~3) \\ x & \equiv 3~(\text{mod}~5) \\ x & \equiv 2~(\text{mod}~7) \end{cases}$$Untuk $M = 3 \times 5 \times 7 = 105$, diperoleh
$$\begin{aligned} M_1 & = \dfrac{105}{3} = 35 \\ M_2 & = \dfrac{105}{5} = 21 \\ M_3 & = \dfrac{105}{7} = 15. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 35^{-1}~(\text{mod}~3) \\ & \equiv 2~(\text{mod}~3) \\ y_2 & \equiv 21^{-1}~(\text{mod}~5) \\ & \equiv 1~(\text{mod}~5) \\ y_3 & \equiv 15^{-1}~(\text{mod}~7) \\ & \equiv 1~(\text{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)~(\text{mod}~105) \\ & \equiv (140 + 63 + 30)~(\text{mod}~105) \\ & \equiv 233~(\text{mod}~105) \\ & \equiv \color{blue}{23}~(\text{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
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 $\cdots \cdot$
A. $18$ C. $22$ E. $82$
B. $20$ D. $52$
Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 2~(\text{mod}~5) \\ x & \equiv 4~(\text{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 & = \dfrac{30}{5} = 6 \\ M_2 & = \dfrac{30}{6} = 5. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 6^{-1}~(\text{mod}~5) \\ & \equiv 1~(\text{mod}~5) \\ y_2 & \equiv 5^{-1}~(\text{mod}~6) \\ & \equiv -1~(\text{mod}~6) \\ & \equiv 5~(\text{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)~(\text{mod}~30) \\ & \equiv 112~(\text{mod}~30) \\ & \equiv 22~(\text{mod}~30). \\ \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 22~(\text{mod}~30).$
Ini berarti, banyaknya sapi paling sedikit adalah $\boxed{22}$ ekor.
(Jawaban C)
Soal Nomor 2
Misalkan $A$ adalah himpunan solusi dari sistem kongruensi
$$\begin{cases} x & \equiv 1~(\text{mod}~2) \\ 2x & \equiv 2~(\text{mod}~5) \\ 10x & \equiv 5~(\text{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 = \cdots \cdot$
A. $960$ D. $984$
B. $972$ E. $988$
C. $982$
Diketahui
$$\begin{cases} x & \equiv 1~(\text{mod}~2) && (\cdots 1) \\ 2x & \equiv 2~(\text{mod}~5) && (\cdots 2) \\ 10x & \equiv 5~(\text{mod}~15) && (\cdots 3) \end{cases}$$Kongruensi $(2)$ dapat disederhanakan menjadi
$$x \equiv 1~(\text{mod}~5),$$sedangkan Kongruensi $(3)$ dapat disederhanakan menjadi
$$\begin{aligned} \dfrac{10}{5}x & \equiv \dfrac55~\left(\text{mod}~\dfrac{15}{5}\right) \\ 2x & \equiv 1~(\text{mod}~3) \\ x & \equiv 2^{-1}~(\text{mod}~3) \\ x & \equiv 2~(\text{mod}~3). \end{aligned}$$Jadi, sistem kongruensi tersebut kita tulis ulang sebagai
$$\begin{cases} x & \equiv 1~(\text{mod}~2) \\ x & \equiv 1~(\text{mod}~5) \\ x & \equiv 2~(\text{mod}~3) \end{cases}$$Karena $\text{FPB}(2, 5) = 1,$ Kongruensi $(1)$ dan $(2)$ dapat disatukan sehingga diperoleh
$$\begin{cases} x & \equiv 1~(\text{mod}~10) \\ x & \equiv 2~(\text{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 & = \dfrac{30}{10} = 3 \\ M_2 & = \dfrac{30}{3} = 10. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 3^{-1}~(\text{mod}~10) \\ & \equiv -3~(\text{mod}~10) \\ & \equiv 7~(\text{mod}~10) \\ y_2 & \equiv 10^{-1}~(\text{mod}~3) \\ & \equiv 1~(\text{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)~(\text{mod}~30) \\ & \equiv (21+20)~(\text{mod}~30) \\ & \equiv 11~(\text{mod}~30). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 11~(\text{mod}~30)$, atau dapat ditulis $x = 30k + 11$ untuk setiap $k \in \mathbb{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 $\boxed{a+b=11+971=982}.$
(Jawaban C)
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 $\cdots \cdot$
A. $42$ C. $62$ E. $82$
B. $52$ D. $72$
Nyatakan dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 1~(\text{mod}~3) \\ x & \equiv 2~(\text{mod}~5) \\ x & \equiv 3~(\text{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 & = \dfrac{105}{3} = 35 \\ M_2 & = \dfrac{105}{5} = 21 \\ M_3 & = \dfrac{105}{7} = 15 \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 35^{-1}~(\text{mod}~3) \\ & \equiv -1~(\text{mod}~3) \\ & \equiv 2~(\text{mod}~3) \\ y_2 & \equiv 21^{-1}~(\text{mod}~5) \\ & \equiv 1~(\text{mod}~5) \\ y_3 & \equiv 15^{-1}~(\text{mod}~7) \\ & \equiv 1~(\text{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)~(\text{mod}~105) \\ & \equiv (70 + 42 + 45)~(\text{mod}~105) \\ & \equiv 157~(\text{mod}~105) \\ & \equiv 52~(\text{mod}~105). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $$\boxed{x \equiv 52~(\text{mod}~105)}.$$Ini berarti, semua bilangan bulat $x$ yang memenuhi kongruensi adalah jawabannya. Pada pilihan B, jelas bahwa $52$ memenuhi.
(Jawaban B)
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 $\left[0, 10^4\right]$ yang menjadi anggota $S$?
A. $433$ D. $833$
B. $633$ E. $834$
C. $832$
Nyatakan $x \in S$ dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 1~(\text{mod}~2) && (\cdots 1) \\ x & \equiv 2~(\text{mod}~3) && (\cdots 2) \\ x & \equiv 3~(\text{mod}~4) && (\cdots 3) \end{cases}$$Perhatikan bahwa $\text{FPB}(2, 4) \neq 1$ sehingga harus dilakukan penyederhanaan lebih dulu.
Dari Kongruensi $(1)$ dan $(3)m$ diperoleh $x = 2k+1 = 4m+3$ untuk suatu bilangan bulat $k, m.$ Sederhanakan dan kita akan peroleh $k = 2m+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~(\text{mod}~4).$ Kita peroleh
$$\begin{cases} x & \equiv 3~(\text{mod}~4) \\ x & \equiv 2~(\text{mod}~3) \end{cases}$$Sekarang, $\{4, 3\}$ relatif prima satu sama lain.
Untuk $M = 4 \times 3 = 12,$ diperoleh
$$\begin{aligned} M_1 & = \dfrac{12}{4} = 3 \\ M_2 & = \dfrac{12}{3} = 4 \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 3^{-1}~(\text{mod}~4) \\ & \equiv -1~(\text{mod}~4) \\ & \equiv 3~(\text{mod}~4) \\ y_2 & \equiv 4^{-1}~(\text{mod}~3) \\ & \equiv 1~(\text{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)~(\text{mod}~12) \\ & \equiv (27+8)~(\text{mod}~12) \\ & \equiv 35~(\text{mod}~12) \\ & \equiv 11~(\text{mod}~12). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $$\boxed{x \equiv 11~(\text{mod}~12)}.$$Karena $S \in \left[0, 10^4\right]$, haruslah $$S = \{11, 23, 35, 47, \cdots, 9995\},$$dengan kardinalitas $\boxed{\text{n}(S) = \dfrac{9995-11}{12}+1 = 833}.$
(Jawaban D)
Soal Nomor 5
Misalkan $$N = 1234567891011\cdots4344$$ 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$
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+\cdots+43+44 & = \dfrac{1+44}{\cancel{2}} \times \cancelto{22}{44} \\ & = \color{blue}{45} \times 22. \end{aligned}$$Jelas bahwa hasilnya habis dibagi $9$ karena salah satu faktornya, $45$, habis dibagi $9.$
Kita peroleh, $N \equiv 0~(\text{mod}~9).$
Selanjutnya, $N$ memiliki satuan $4$ sehingga $N \equiv 4~(\text{mod}~5)$.
Kita peroleh dua kongruensi linear yang membentuk sebuah sistem.
$$\begin{cases} N & \equiv 0~(\text{mod}~9) \\ N & \equiv 4~(\text{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 & ~\text{tidak perlu dicari} \\ M_2 & = \dfrac{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~(\text{mod}~5)$.
Berdasarkan teorema sisa Cina, kita dapatkan solusi
$$\begin{aligned} x & \equiv (\color{blue}{0}+ 4 \cdot 9 \cdot 4)~(\text{mod}~45) \\ & \equiv (144)~(\text{mod}~45) \\ & \equiv 9~(\text{mod}~45). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $$\boxed{N \equiv 9~(\text{mod}~45)}.$$ Ini menunjukkan bahwa $N$ memiliki sisa $9$ jika dibagi $45.$
(Jawaban C)
Baca Juga: Perhitungan Modulo pada ISBN
Soal Nomor 6
Dalam bentuk desimal, bilangan $N = 99999\cdots999$ terdiri dari $2.020$ buah angka $9.$ Jika $N$ dibagi $2.020,$ maka sisanya $\cdots \cdot$
A. $1.818$ D. $2.018$
B. $1.918$ E. $2.019$
C. $1.919$
Perhatikan bahwa
$$\begin{aligned} 99 & = 10^2-1 \\ 999 & = 10^3-1 \\ 9999 & = 10^4-1. \end{aligned}$$Berdasarkan pola yang ada, haruslah
$N = \underbrace{99999\cdots999}_{\text{ada}~2.020} = 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~(\text{mod}~4) && (\cdots 1) \\ 10^{2020} & \equiv 0~(\text{mod}~5) && (\cdots 2) \\ 10^{2.020} = 100^{1.010} & \equiv (-1)^{1.010}~(\text{mod}~101) \equiv 1~(\text{mod}~101) && (\cdots 3). \end{cases}$$Untuk $M = 4 \times 5 \times 101 = 2.020,$ diperoleh
$$\begin{aligned} M_1 & = \dfrac{2.020}{4} = 505 \\ M_2 & = \dfrac{2.020}{5} = 404 \\ M_3 & = \dfrac{2.020}{101} = 20. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 505^{-1}~(\text{mod}~4) \\ & \equiv 1~(\text{mod}~4) \\ y_2 & \equiv 404^{-1}~(\text{mod}~5) \\ & \equiv 4~(\text{mod}~5)\\ y_3 & \equiv 20^{-1}~(\text{mod}~101) \\ & \equiv 96~(\text{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)~(\text{mod}~2.020) \\ & \equiv 1920~(\text{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 $\boxed{1.919}.$
(Jawaban C)
Bagian Uraian
Soal Nomor 1
Carilah solusi dari sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 3~(\text{mod}~4) \\ x & \equiv 2~(\text{mod}~3) \\ x & \equiv 4~(\text{mod}~5) \end{cases}$$
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 & = \dfrac{60}{4} = 15 \\ M_2 & = \dfrac{60}{3} = 20 \\ M_3 & = \dfrac{60}{5} = 12 \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 15^{-1}~(\text{mod}~4) \\ & \equiv 3~(\text{mod}~4) \\ y_2 & \equiv 20^{-1}~(\text{mod}~3) \\ & \equiv 2~(\text{mod}~3) \\ y_3 & \equiv 12^{-1}~(\text{mod}~5) \\ & \equiv 3~(\text{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)~(\text{mod}~60) \\ & \equiv (135 + 80 + 144)~(\text{mod}~60) \\ & \equiv (15 + 20 + 24)~(\text{mod}~60) \\ & \equiv 59~(\text{mod}~60). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $\boxed{x \equiv 59~(\text{mod}~60)}.$
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)?
Misalkan $x$ menyatakan banyaknya tentara di lapangan. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 1~(\text{mod}~4) \\ x & \equiv 2~(\text{mod}~5) \\ x & \equiv 4~(\text{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 & = \dfrac{140}{4} = 35 \\ M_2 & = \dfrac{140}{5} = 28 \\ M_3 & = \dfrac{140}{7} = 20. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 35^{-1}~(\text{mod}~4) \\ & \equiv -1~(\text{mod}~4) \\ & \equiv 3~(\text{mod}~4) \\ y_2 & \equiv 28^{-1}~(\text{mod}~5) \\ & \equiv 2~(\text{mod}~5) \\ y_3 & \equiv 20^{-1}~(\text{mod}~7) \\ & \equiv -1~(\text{mod}~7) \\ & \equiv 6~(\text{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)~(\text{mod}~140) \\ & \equiv (105 + 112 + 480)~(\text{mod}~140) \\ & \equiv 697~(\text{mod}~140) \\ & \equiv 137~(\text{mod}~140). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 137~(\text{mod}~140).$
Ini berarti, paling sedikit ada $\boxed{137}$ tentara di lapangan tersebut.
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.
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~(\text{mod}~3) \\ x & \equiv 1~(\text{mod}~4) \\ x & \equiv 4~(\text{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 & = \dfrac{60}{3} = 20 \\ M_2 & = \dfrac{60}{4} = 15 \\ M_3 & = \dfrac{60}{5} = 12. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 20^{-1}~(\text{mod}~3) \\ & \equiv 2~(\text{mod}~3) \\ y_2 & \equiv 15^{-1}~(\text{mod}~4) \\ & \equiv 3~(\text{mod}~4) \\ y_3 & \equiv 12^{-1}~(\text{mod}~5) \\ & \equiv 3~(\text{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)~(\text{mod}~60) \\ & \equiv (0 + 45 + 144)~(\text{mod}~60) \\ & \equiv 189~(\text{mod}~60) \\ & \equiv 9~(\text{mod}~60). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 9~(\text{mod}~60).$
Ini berarti, hari berikutnya ketika ketiga sistem irigasi tersebut bekerja secara bersamaan adalah hari ke-9.
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.
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~(\text{mod}~6) \\ x & \equiv 4~(\text{mod}~7) \\ x & \equiv 9~(\text{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 & = \dfrac{462}{6} = 77 \\ M_2 & = \dfrac{462}{7} = 66 \\ M_3 & = \dfrac{462}{11} = 42. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 77^{-1}~(\text{mod}~6) \\ & \equiv 5~(\text{mod}~6) \\ y_2 & \equiv 66^{-1}~(\text{mod}~7) \\ & \equiv 5~(\text{mod}~7) \\ y_3 & \equiv 42^{-1}~(\text{mod}~11) \\ & \equiv 5~(\text{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)~(\text{mod}~462) \\ & \equiv (0 + 1.320 + 1.890)~(\text{mod}~462) \\ & \equiv 3.210~(\text{mod}~462) \\ & \equiv 438~(\text{mod}~462). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 438~(\text{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.
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?
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~(\text{mod}~5) \\ x & \equiv 3~(\text{mod}~6) \\ x & \equiv 1~(\text{mod}~7) \\ x & \equiv 0~(\text{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 & = \dfrac{2.310}{5} = 462 \\ M_2 & = \dfrac{2.310}{6} = 385 \\ M_3 & = \dfrac{2.310}{7} = 330 \\ M_4&~\text{tidak perlu dicari}. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 462^{-1}~(\text{mod}~5) \\ & \equiv -2~(\text{mod}~5) \\ & \equiv 3~(\text{mod}~5) \\ y_2 & \equiv 385^{-1}~(\text{mod}~6) \\ & \equiv 1~(\text{mod}~6) \\ y_3 & \equiv 330^{-1}~(\text{mod}~7) \\ & \equiv 1~(\text{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 + \color{red}{0})~(\text{mod}~2.310) \\ & \equiv (4.158+ 1.155 + 330)~(\text{mod}~2.310) \\ & \equiv 5.643~(\text{mod}~2.310) \\ & \equiv 1.023~(\text{mod}~2.310). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 1.023~(\text{mod}~2.310).$
Karena $1.023 < 1.200$ (jumlah tentara semula), jumlah tentara yang selamat sebanyak $\boxed{1.023}$ orang.
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?
Misalkan $x$ menyatakan bilangan “aku”. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 4~(\text{mod}~5) \\ x & \equiv 3~(\text{mod}~6) \\ x & \equiv 9~(\text{mod}~11) \\ x & \equiv 2~(\text{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 & = \dfrac{5.610}{5} = 1.122 \\ M_2 & = \dfrac{5.610}{6} = 935 \\ M_3 & = \dfrac{5.610}{11} = 510 \\ M_4 & = \dfrac{5.610}{17} = 330. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 1.122^{-1}~(\text{mod}~5) \\ & \equiv -2~(\text{mod}~5) \\ & \equiv 3~(\text{mod}~5) \\ y_2 & \equiv 935^{-1}~(\text{mod}~6) \\ & \equiv -1~(\text{mod}~6) \\ & \equiv 5~(\text{mod}~6) \\ y_3 & \equiv 510^{-1}~(\text{mod}~11) \\ & \equiv 3~(\text{mod}~11) \\ y_4 & \equiv 330^{-1}~(\text{mod}~17) \\ & \equiv 5~(\text{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)~(\text{mod}~5.610) \\ & \equiv (13.464+14.025 +22.950+2.300)~(\text{mod}~5.610) \\ & \equiv 44.559~(\text{mod}~5.610) \\ & \equiv 5.289~(\text{mod}~5.610). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 5.289~(\text{mod}~5.610)$. Karena aku adalah bilangan terkecil yang memenuhi kriteria di atas, aku adalah bilangan $\boxed{5.289}.$
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?
Misalkan $x$ menyatakan banyaknya ikan cupang di dalam akuarium. Permasalahan di atas dapat dinyatakan dalam sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv 1~(\text{mod}~2) \\ x & \equiv 1~(\text{mod}~3) \\ x & \equiv 1~(\text{mod}~5) \\ x & \equiv 1~(\text{mod}~7) \\ x & \equiv 0~(\text{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 & = \dfrac{2.310}{2} = 1.155 \\ M_2 & = \dfrac{2.310}{3} = 770 \\ M_3 & = \dfrac{2.310}{5} = 462 \\ M_4 & = \dfrac{2.310}{7} = 330 \\ M_5&~\text{tidak perlu dicari}. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 1.155^{-1}~(\text{mod}~2) \\ & \equiv 1~(\text{mod}~2) \\ y_2 & \equiv 770^{-1}~(\text{mod}~3) \\ & \equiv 2~(\text{mod}~3) \\ y_3 & \equiv 462^{-1}~(\text{mod}~5) \\ & \equiv 3~(\text{mod}~5) \\ y_4 & \equiv 330^{-1}~(\text{mod}~5) \\ & \equiv 1~(\text{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 + \color{red}{0})~(\text{mod}~2.310) \\ & \equiv (4.411)~(\text{mod}~2.310) \\ & \equiv 2.101~(\text{mod}~2.310). \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 2.101~(\text{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 $\boxed{2.101}$ ekor.