Salah seorang matematikawan dari china ch’in chiu Shao pernah melontarkan sebuah pertanyaan :
“Jika suatu bilangan dibagi 3 maka bersisa 1, jika dibagi 5 bersisa 2 dan jika dibagi 7 bersisa 3. Berapakah bilangan tersebut?”
Pertanyaan tersebut dapat ditulis :
x º 1 (mod 3)
x º 2 (mod 5)
x º 3 (mod 7)
berikut langkah penyelesaian dari soal tersebut.
Cara 1
x º 1 (mod 3)
perkongruenan tersebut berarti :
x = 1 + 3a ..................... (1)
persamaan (1) tersebut kita substitusikan ke x º 2 (mod 5)
x º 2 (mod 5)
1 + 3a º 2 (mod 5) kedua ruas dikurangi dengan 1
1 + 3a – 1 º 2 – 1 (mod 5)
3a º 1 (mod 5) ruas kanan ditambah dengan 5
3a º 1 + 5 (mod 5)
3a º 6 (mod 5)
3a º 3.2 (mod 5) kedua ruas dibagi 3
a º 2 (mod 5)
perkongruenan ini berarti :
a = 2 + 5b .................... (2)
persamaan (2) disubstitusikan ke persamaan (1) diperoleh :
x = 1 + 3a
x = 1 + 3(2 + 5b)
x = 1 + 6 + 15 b
x = 7 + 15b ....................(3)
persamaan (3) disubstitusikan ke perkongruenan x º 3 (mod 7)
x º 3 (mod 7)
7 + 15b º 3 (mod 7) kedua ruas dikurangi dengan 7
7 + 15b – 7 º 3 – 7 (mod 7)
15b º -4 (mod 7) ruas kanan ditambahkan dengan 7x7
15b º -4 + 7.7 (mod 7)
15b º -4 + 49 (mod 7)
15b º 45 (mod 7)
15b º 15. 3 (mod 7) bagi kedua ruas dengan 15
b º 3 (mod 7)
perkongruenan ini berarti :
b = 3 + 7c .................. (4)
persamaan (4) ini kita substitusikan ke persamaan (3) maka diperoleh :
x = 7 + 15(3 + 7c)
x = 7 + 45 + 105c
x = 52 + 105c .............. (5)
persamaan (5) ini dapat ditulisa dalam bentuk :
x º 52 (mod 105)
jadi bilangan tersebut adalah 52
bisa dilihat bahwa jika 52 dibagi 3 maka akan bersisa 1, jika dibagi 5 akan bersisa 2 dan jika dibagi 7 akan bersisa 3.
Cara lain untuk menyelesaiakan soal tersebut di atas bisa dilihat dengan cara 2 berikut ini.
Cara 2
x º 1 (mod 3)
x º 2 (mod 5)
x º 3 (mod 7)
misalnya :
a1 = 1 m1 = 3 M1 = m2 x m3 = 5 x 7 = 35
a2 = 2 m2 = 5 M2 = m1 x m3 = 3 x 7 = 21
a3 = 3 m3 = 7 M3 = m1 x m2 = 3 x 5 = 15
dari nilai M1,M2 dan M3 maka dapat ditulis :
M1x = 35x º 1 (mod 3) ruas kanan ditambahkan dengan 3 x 23
35x º 1 + 3.23 (mod 3)
35x º 70 (mod 3) kedua ruas dibagi 35
x º 2 (mod 3)
kita peroleh s1 = 2
M2x = 21x º 1 (mod 5) ruas kanan ditambah dengann 4 x 5
21x º 1 + 4.5 (mod 5)
21x º 21 (mod 5) kedua ruas dibagi 21
x º 1 (mod 5)
diperoleh s2 = 1
M3x = 15x º 1 (mod 7) ruas kanan ditambah dengan 7 x 2
15x º 1 + 7.2 (mod 7)
15x º 15 (mod 7) kedua ruas dibagi dengan 15
x º 1 (mod 7)
diperoleh s3 =1
untuk mencari hasil akhir maka kita gunakan rumus :
s = a1s1M1 + a2s2M2 + a3s3M3
s = 1.2.35 + 2.1.21 + 3.1.15
s = 70 + 42 + 45
s = 157
maka sistem perkonrunan di atas dapat ditulis :
x º s (mod m1m2m3)
x º 157 (mod 3.5.7)
x º 157 (mod 105)
x º 157 – 105 (mod 105)
x º 52 (mod 105)
jadi bilangan tersebut adalah 52.
