Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas Chinese Reminder Theorem yang menjelaskan tentang sistem kongruensi linier dan cara mencari solusi uniknya. Teorema ini melibatkan bilangan asli pairwise relatively prime M1, M2, M3, ..., Mn dan bilangan bulat A1, A2, A3, ..., An. Dengan menggunakan teorema ini, kita dapat menemukan solusi unik modulo M yang merupakan perkalian dari M1, M2, M3, ..., Mn. Proses pembuktian teorema melibatkan definisi Mk, pencarian bilangan Yk sebagai invers dari M besar k, dan penentuan solusi simultan X yang memenuhi semua kongruensi linier yang diberikan. Dengan demikian, X dapat ditemukan sebagai solusi dari sistem kongruensi linier yang diberikan dengan modulo M yang sesuai.

Sekarang kita lanjutkan mengenai Chinese Reminder Theorem.

Jadi kalau di dalam persamaan linier itu kita bisa mendapatkan sistem persamaan linier.

Kalau kamu belajar aljabar linier disitu suruh mencari solusinya.

Nah kalau disini kita juga bisa mendapatkan beberapa kongruensi linier,

kemudian kita mau mencari berapa nilai X yang memenuhi semua kongruensi linier yang diberikan.

Jadi teoremanya ini mengatakan seperti ini,

misalkan kita punya ada M1, M2, M3, dan Mn bilangan asli yang lebih besar dari 1

dan memenuhi pairwise relatively prime, artinya sepasang-sepasang itu prima relatif,

kemudian kita punya A1, A2, A3, sampai An itu bilangan bulat,

maka sistem kongruensi linier X kongruen AI modulo MI untuk I nya 1, 2, 3, sampai N

dia akan mempunyai solusi yang unik modulo M dengan M nya itu nanti merupakan perkalian dari M1, M2, M3, sampai Mn.

Jadi disini terdapat solusi X dimana X nya itu lebih besar sama dengan 0 tapi lebih kecil M

karena kita bekerja terhadap modulo M dan semua solusi lain yang kongruen modulo M terhadap solusi tersebut.

Jadi istilah unik modulo M itu terkait dengan M nya nilainya itu 1 tapi bisa merupakan kelipatan M sendiri.

Bagaimana cara menunjukkan atau membuktikan teorema ini bahwa kita bisa mendapatkan solusi

yang pertama kita membuat dulu M nya itu kan hasil kali dari M kecil disini M1, M2, M3, sampai Mn.

Sekarang kita define dulu Mk, M nya disini besar untuk menyatakan bilangan M dibagi Mk.

Jadi Mk itu adalah perkalian dari M1, M2, sampai Mn kecuali Mk.

Jadi kalau kita cari M1, M1 itu adalah M2 kali M3 kali M4 sampai Mn.

M2 itu nanti akan sama dengan M1 kali M3 kali M4 sampai Mn.

Karena Mi dan Mk tidak memiliki pembagian persekutuan karena dia adalah relatif prima

maka GCD nya si Mk dengan si M yang besar k itu juga sama dengan 1.

Nah berdasarkan teorema yang terkait dengan inverse kita akan bisa mencari suatu bilangan bulat

yang kita sebut sebagai Yk yang ini inverse perkalian modulo Mk untuk si M besar k tadi

berarti M besar k dikali Yk itu akan kongruen dengan 1 modulo Mk yang M nya kecil.

Jadi si Yk ini adalah inverse untuk M yang besar.

Kemudian kita definisikan si X sebagai penjumlahan tadi kita punya M1, Y1, M2, Y2 dan seterusnya

disini dikasih koefisien A1, A2, A3 dan seterusnya kita akan mendapatkan suatu persamaan.

Langkah berikutnya adalah kita mau menunjukkan si X yang kita definisikan ini merupakan solusi simultan dari yang tadi X

kongruen modulo M1, modulo M2, modulo M3 sampai modulo Mn.

Sekarang kita perhatikan si Mj, Mj ini kan tadi merupakan M dibagi Mj

berarti dia kan kalau dicari untuk modulo Mk itu ada kongruen 0 modulo Mk

disini tentunya J nya tidak boleh sama dengan K

Mkyk tadi Yk nya adalah inverse dari si Mk sehingga Mk x Yk itu kongruen dengan 1 modulo Mk

sehingga X itu akan sama dengan Ak x Mk, M besar disini dikali Yk

atau kita bisa menuliskannya sebagai Ak modulo Mk

untuk sembarang K dalam hari ini K nya bisa 1, 2, 3 sampai N

dengan demikian X nya itu merupakan solusi simultan untuk N buah kongruensi

jadi perlu diingat lagi bahwa X nya tadi kita definisikan si Ai nya itu berasal dari kongruensi linier yang diberikan

jadi misalnya mau diberikan 10 berarti kita punya A1 sampai A10 dan seterusnya

jadi disini kita bisa mencari solusinya X nya itu adalah kongruen dengan Ak modulo M

dan X nya itu merupakan bilangan, ini bilangannya kan perkalian dan penjumlahan itu nanti unik

cuma karena kita bicara dengan modulo M nanti kita bisa mendapat bilangan-bilangan lain yang ekivalen atau kongruen dengan bilangan tersebut