Materi, Soal, dan Pembahasan – Teorema Sisa Cina

Pada zaman dahulu, orang-orang “beruntung” menemui masalah dalam hidupnya terkait sisa hasil bagi. Hal ini terjadi ketika mereka tidak mengetahui banyak barang yang dimiliki, tetapi mereka memiliki sejumlah informasi bahwa ketika banyak 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 (TSC), Anda diwajibkan (WAJIB! Tidak ada kompromi) mempelajari materi kongruensi modulo dan inversnya 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 (TSC). 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 negara Cina.

Teorema Sisa Cina

Misalkan $m_1, m_2, \cdots, m_r$ adalah bilangan bulat positif sedemikian sehingga $\text{FPB}(m_i, m_j) = 1$ untuk $i \neq j$. Sistem kongruensi linear satu variabel
$$\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.

Bukti

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
$$\begin{aligned} \overline{x} & \equiv a_1M_1x_1 + a_2M_2x_2 + \cdots + a_rM_rx_r \\ & \equiv a_kM_kr_k~(\text{mod}~m_k) \end{aligned}$$adalah solusi simultan dari sistem yang diberikan.
Pertama, amati bahwa $M_i \equiv 0~(\text{mod}~m_k)$ untuk $i \neq k.$ Karena $m_k~|~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_k). \end{aligned}$$Pilih bilangan bulat $x_k$ sedemikian sehingga $M_kx_k \equiv 1~(\text{mod}~m_k).$
Oleh karena itu, kita dapatkan
$$\begin{aligned} \overline{x} & \equiv a_k(1)~(\text{mod}~m_k) \\ & \equiv a_k~(\text{mod}~m_k). \end{aligned}$$Ini menunjukkan bahwa sistem kongruensi tersebut memiliki solusi.
Untuk menunjukkan ketunggalannya, misalkan $x’$ adalah sembarang bilangan bulat yang memenuhi sistem kongruensi tersebut sehingga
$$\overline{x} \equiv a_k \equiv x’~(\text{mod}~m_k), 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’)$, berakibat $\overline{x} \equiv x’~(\text{mod}~n_k)$. $\blacksquare$

[collapse]

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

  1. 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}$$
  2. Pastikan bahwa $\{m_1, m_2, \cdots, m_r\}$ semuanya saling relatif prima (memiliki FPB $1$). Jika tidak, sederhanakan terlebih dahulu sistem tersebut dengan menggunakan sifat-sifat kongruensi modulo.
  3. Tuliskan $x_k \equiv M_k^{-1}~(\text{mod}~m_k)$ dan selesaikan invers modulo tersebut.
  4. Nyatakan solusi sistem sebagai
    $$\begin{aligned} x & \equiv \displaystyle \sum_{i=1}^r (a_iM_ix_i)~(\text{mod}~N_k) \\ & \equiv (a_1M_1x_1 + a_2M_2x_2 + \cdots + a_rM_rx_r)~(\text{mod}~N_k). \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 banyak 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 Euclid

     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 $\cdots \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~(\text{mod}~5) \\ x & \equiv 4~(\text{mod}~6) \end{cases}$$Perhatikan bahwa $\{5, 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 banyak sapi paling sedikit adalah $\boxed{22}$ ekor.
(Jawaban C)

[collapse]

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$

Pembahasan

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$, maka 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, 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)

[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 $\cdots \cdot$
A. $42$                     C. $62$                      E. $82$
B. $52$                    D. $72$

Pembahasan

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, 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)

[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 $\left[0, 10^4\right]$ 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~(\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)$, diperoleh $x = 2k+1 = 4m+3$ untuk suatu $k, m$ bilangan bulat. 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]$, maka $$S = \{11, 23, 35, 47, \cdots, 9995\},$$dengan kardinalitas $\boxed{\text{n}(S) = \dfrac{9995-11}{12}+1 = 833}$
(Jawaban D)

[collapse]

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$

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 takhabis 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, 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$ nanti 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)

[collapse]

Baca Juga: Perhitungan Modulo pada ISBN 

Soal Nomor 6

Dalam bentuk desimal, bilangan $N = 99999\cdots999$ terdiri dari $2020$ buah angka $9$. Jika $N$ dibagi $2020$, maka sisanya $\cdots \cdot$
A. $1818$                      D. $2018$
B. $1918$                      E. $2019$
C. $1919$

Pembahasan

Perhatikan bahwa
$$\begin{aligned} 99 & = 10^2-1 \\ 999 & = 10^3-1 \\ 9999 & = 10^4-1 \end{aligned}$$Berdasarkan pola yang ada, maka $N = \underbrace{99999\cdots999}_{\text{ada}~2020} = 10^{2020}-1.$
Misalkan $X = 10^{2020}$. Perhatikan bahwa $2020 = 4 \times 5 \times 101.$ Gunakan TSC dengan menganggap $10^{2020}$ sebagai salah satu solusi dari sistem kongruensi modulo, yaitu
$$\begin{cases} 10^{2020} & \equiv 0~(\text{mod}~4) && (\cdots 1) \\ 10^{2020} & \equiv 0~(\text{mod}~5) && (\cdots 2) \\ 10^{2020} = 100^{1010} & \equiv (-1)^{1010}~(\text{mod}~101) \equiv 1~(\text{mod}~101) && (\cdots 3) \end{cases}$$Untuk $M = 4 \times 5 \times 101 = 2020$, diperoleh
$$\begin{aligned} M_1 & = \dfrac{2020}{4} = 505 \\ M_2 & = \dfrac{2020}{5} = 404 \\ M_3 & = \dfrac{2020}{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}~2020) \\ & \equiv 1920~(\text{mod}~2020) \\ \end{aligned}$$Jadi, $X = 10^{2020}$ dibagi oleh $2020$ bersisa $1920$. Artinya, $N = 10^{2020}-1$ dibagi oleh $2020$ bersisa $\boxed{1919}$
(Jawaban C)

[collapse]

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}$$

Pembahasan

Perhatikan bahwa $\{3, 4, 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)}$

[collapse]

Soal Nomor 2

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

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

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

Pembahasan

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, 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)$.
Kembali pada persoalan, ini berarti paling sedikit ada $\boxed{137}$ tentara di lapangan tersebut.

[collapse]

Soal Nomor 3

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

  1. Jika disusun dalam baris berbanjar lima, maka $3$ tentara tidak memiliki baris.
  2. Jika disusun dalam baris berbanjar $6$, maka $3$ tentara tidak memiliki baris.
  3. Jika disusun dalam baris berbanjar $7$, maka $1$ tentara tidak memiliki baris.
  4. Jika disusun dalam baris berbanjar $11$, maka tidak ada tentara yang tersisa.

Berapakah jumlah tentara yang selamat?

Pembahasan

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, 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), ini berarti jumlah tentara yang selamat sebanyak $\boxed{1.023}$ orang.

[collapse]

Soal Nomor 4

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

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, 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}$

[collapse]