Materi, Soal, dan Pembahasan – Teorema Sisa Cina

     Pada zaman dahulu, orang-orang “beruntung” menemui masalah terkait sisa hasil bagi dalam hidupnya. 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 tak 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$ 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, 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:
“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, namun tanpa solusi, sehingga menimbulkan ketertarikan untuk menyelesaikannya.

        Sekitar abad ke-6, 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 teori kongruensi linear, hal ini memungkinkan untuk menyelesaikan kongruensi $M_kx \equiv 1~(\text{mod}~m_k)$. Sebut saja $x_k$ sebagai solusi tunggalnya. Tujuannya 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$, sehingga 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 akan memperoleh
$$\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 selanjutnya $m_k~|~(\overline{x}-x’)$ untuk setiap nilai $k$. Karena $\text{FPB}(m_i, m_j) = 1$, maka 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 $$\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 berikut jika Anda masih belum memahami bagaimana cara mendapatkan bilangan $2, 1$, dan $1$ di atas.
Berdasarkan Teorema Sisa Cina, sekarang 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, sekarang 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 tinggal menggunakan 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, sekarang 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 bila 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, sekarang 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 bila dibagi $2$ bersisa 1, dibagi $3$ bersisa $2$, dan 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 akan diperoleh $k = 2m+1$. Ini menunjukkan bahwa nilai $k$ bergantung pada nilai $m$. Apapun nilai bulat $m$, maka $k$ juga akan bulat. Oleh karena itu, kedua kongruensi tersebut disederhanakan menurut kongruensi $(3)$, yakni $x \equiv 3~(\text{mod}~4)$. Diperoleh
$$\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, sekarang 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$ bila satuannya $0$ atau $5$. Dari sini, kita juga sekaligus dapat menentukan sisa hasil baginya jika tak 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, 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, sekarang kita dapatkan solusi

$$\begin{aligned} x & \equiv (\color{blue}{0}+ 4 \cdot 9 \cdot 4)~(\text{mod}~45) \\ & \equiv (145)~(\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$ bila dibagi $45$.
(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, sekarang 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.
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

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, sekarang 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 $1200$ tentara dalam perang tersebut.
Jika disusun dalam baris berbanjar lima, maka $3$ tentara tidak memiliki baris.
Jika disusun dalam baris berbanjar $6$, maka $3$ tentara tidak memiliki baris.
Jika disusun dalam baris berbanjar $7$, maka $1$ tentara tidak memiliki baris.
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 = 2310$, diperoleh

$$\begin{aligned} M_1 & = \dfrac{2310}{5} = 462 \\ M_2 & = \dfrac{2310}{6} = 385 \\ M_3 & = \dfrac{2310}{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, sekarang 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}~2310) \\ & \equiv (4158+ 1155 + 330)~(\text{mod}~2310) \\ & \equiv 5643~(\text{mod}~2310) \\ & \equiv 1023~(\text{mod}~2310) \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 1023~(\text{mod}~2310)$.
Karena $1023 < 1200$ (jumlah tentara semula), ini berarti jumlah tentara yang selamat sebanyak $\boxed{1023}$ orang.

[collapse]

Soal Nomor 4
Aku adalah bilangan terkecil yang:
bila dibagi $5$, bersisa $4$;
bila dibagi $6$, bersisa $3$;
bila dibagi $11$, bersisa $9$;
bila 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 = 5610$, diperoleh

$$\begin{aligned} M_1 & = \dfrac{5610}{5} = 1122 \\ M_2 & = \dfrac{5610}{6} = 935 \\ M_3 & = \dfrac{5610}{11} = 510 \\ M_4 & = \dfrac{5610}{17} = 330 \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 1122^{-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}$$Catatan:
Berdasarkan Teorema Sisa Cina, sekarang kita dapatkan solusi
$$\begin{aligned} x & \equiv (4 \cdot 1122 \cdot 3 + 3 \cdot 935 \cdot 5 + 9 \cdot 510 \cdot 3 + 2 \cdot 330 \cdot 5)~(\text{mod}~5610) \\ & \equiv (13464+14025 +22950+2300)~(\text{mod}~5610) \\ & \equiv 44559~(\text{mod}~5610) \\ & \equiv 5289~(\text{mod}~5610) \end{aligned}$$Jadi, solusi dari sistem kongruensi linear tersebut adalah $x \equiv 5289~(\text{mod}~5610)$. Karena aku adalah bilangan terkecil yang memenuhi kriteria di atas, maka aku adalah bilangan $\boxed{5289}$

[collapse]

Tinggalkan Balasan

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *