contoh soal Teorema Sisa Cina (Chinese Remainder Theorem / CRT) beserta penyelesaiannya langkah demi langkah, dari yang sederhana sampai agak menantang.

Contoh Soal 1 (Dasar)

Soal:
Tentukan bilangan bulat positif terkecil $x$x yang memenuhi:$$\begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 2 \pmod{4} \end{cases}$${x≡1(mod3)x≡2(mod4)​

Penyelesaian:

Cari bilangan yang memenuhi kedua syarat.

• Dari $x \equiv 1 \pmod{3}$x≡1(mod3):
  $x = 1, 4, 7, 10, 13, \dots$x=1,4,7,10,13,…
• Dari $x \equiv 2 \pmod{4}$x≡2(mod4):
  $x = 2, 6, 10, 14, \dots$x=2,6,10,14,…

Bilangan yang sama adalah 10

Baca juga:FEB Universitas Teknokrat Indonesia Gelar Kuliah Umum Ekonomi Mikro Bahas Peran Pemerintah dalam Penyediaan Barang Publik

Jawaban:$$x = 10$$x=10

Contoh Soal 2 (Menggunakan Rumus CRT)

Soal:
Tentukan solusi dari sistem kongruensi:$$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \end{cases}$${x≡2(mod3)x≡3(mod5)​

Penyelesaian:

1. Tentukan hasil kali modulus:

$$M = 3 \times 5 = 15$$M=3×5=15

2. Hitung:

$$M_1 = \frac{M}{3} = 5, \quad M_2 = \frac{M}{5} = 3$$M1​=3M​=5,M2​=5M​=3

3. Cari invers modulo:

• Invers $5 \mod 3 = 2$5mod3=2, karena $5 \cdot 2 \equiv 1 \pmod{3}$5⋅2≡1(mod3)
• Invers $3 \mod 5 = 2$3mod5=2, karena $3 \cdot 2 \equiv 1 \pmod{5}$3⋅2≡1(mod5)

4. Gunakan rumus:

$$x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15}$$x≡(2⋅5⋅2)+(3⋅3⋅2)(mod15)$$x \equiv 20 + 18 = 38 \equiv 8 \pmod{15}$$x≡20+18=38≡8(mod15)

Jawaban:$$x = 8$$x=8

Contoh Soal 3 (Soal Cerita)

Soal:
Seorang pedagang memiliki sejumlah barang.

• Jika dibagi 4, sisa 1
• Jika dibagi 5, sisa 3
• Jika dibagi 6, sisa 5

Tentukan jumlah barang paling sedikit yang mungkin.

Penyelesaian:

Bentuk kongruensi:$$\begin{cases} x \equiv 1 \pmod{4} \\ x \equiv 3 \pmod{5} \\ x \equiv 5 \pmod{6} \end{cases}$$⎩⎨⎧​x≡1(mod4)x≡3(mod5)x≡5(mod6)​

Cari bilangan yang memenuhi:

• Dari mod 4: 1, 5, 9, 13, 17, 21, 25, 29, …
• Cek mod 5 dan mod 6

Bilangan 29 memenuhi semua syarat.

Jawaban:$$x = 29$$x=29

Baca juga:Belajar Lebih Interaktif di Era Digital: Contoh Soal Kelas Maya dan

Contoh Soal 4 (Tingkat Menengah)

Soal:
Tentukan solusi dari:$$\begin{cases} x \equiv 4 \pmod{7} \\ x \equiv 5 \pmod{9} \end{cases}$${x≡4(mod7)x≡5(mod9)​

Penyelesaian Singkat:

• $M = 7 \times 9 = 63$M=7×9=63
• $M_1 = 9$M1​=9, invers $9 \mod 7 = 4$9mod7=4
• $M_2 = 7$M2​=7, invers $7 \mod 9 = 4$7mod9=4

$$x \equiv (4 \cdot 9 \cdot 4) + (5 \cdot 7 \cdot 4)$$x≡(4⋅9⋅4)+(5⋅7⋅4)$$x \equiv 144 + 140 = 284 \equiv 32 \pmod{63}$$x≡144+140=284≡32(mod63)

Jawaban:$$x = 32$$x=32

Penulis: loveytha