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

Video ini membahas kongruensi linier, Chinese Reminder Theorem, dan Fermat Litter Theorem dalam Matematika Diskrit. Kongruensi linier digunakan untuk mencari inverse, seperti inverse perkalian modulo M. Penyelesaiannya melibatkan inverse modulo M, metode backwards, dan algoritma Euclid. Teorema 1 merangkum bahwa jika A dan M relatif prima dengan M lebih besar dari 1, maka akan ada inverse A bar sehingga A bar kali A kongruen dengan 1 modulo M. Penjelasan juga diberikan mengenai kapan suatu elemen memiliki inverse, contohnya dalam modulo 4. Inversenya unik jika terhadap modulo M, seperti yang ditunjukkan dalam penjelasan mengenai uniknya inverse dalam kongruensi linier.

Kali ini kita akan membahas tentang kongruensi linier, Chinese Reminder Theorem dan Fermat Litter Theorem.

Kongruensi linier ini salah satunya adalah untuk mencari inverse.

Jadi kalau kita bicara tentang bilangan real, inverse 2 itu setengah biasanya karena 2 x 1 setengah itu sama dengan 1.

Kalau kita bicara mengenai himpunan bilangan bulat, maka 2 itu tidak punya inverse terhadap perkalian

karena 2 itu dikalikan berapapun yang berapapunnya ini bilangan bulat ya, itu tidak mungkin sama dengan 1.

Untuk yang operasi yang menggunakan modulo, maka suatu bilangan di sini dikasih notasinya A pakai bar di atasnya

disebut sebagai inverse perkalian modulo M untuk elemen A, kalau A dikali A barnya tadi itu kongruen dengan 1 modulo M.

Sebagai contoh, misalnya kalau kita punya elemen 3 inversenya berapa untuk modulo 7?

Ternyata 5 adalah inverse perkalian modulo 7 untuk 3 karena 3 x 5 itu kan sama dengan 15, 15 itu kongruen dengan 1 modulo 7.

Jadi 5 adalah inverse dari 3, begitu juga 3 itu juga inverse dari 5 karena kebetulan ini komutatif ya, jadi bisa pindah tempat.

Kalau di dalam persamaan biasa itu kita punya yang kita sebut sebagai persamaan linier,

jadi misalnya 2x sama dengan 1, x nya berapa? Kita bisa cari x nya setengah tinggal dibagi.

Kata dibagi itu sebetulnya dikali dengan inversenya, jadi 2x sama dengan 1 itu x nya sama dengan 1 dikali sama si inversenya si 2 tadi yaitu setengah,

Sekarang kalau kita punya kongruensinya dalam bentuk linier, jadi persamaannya itu Ax kongruen B modulo M,

di sini tidak persis persamaan ya, tapi ini mirip dengan persamaan linier,

dimana M nya itu anggota bilangan bulat yang positif, AB nya itu masuk di dalam himpunan bilangan bulat,

dan x nya adalah variable, itu kita sebut sebagai kongruensi linier.

Jadi Ax kongruen dengan B modulo M itu disebut kongruensi linier.

Bagaimana menyelesaikan kongruensi linier itu?

Kita akan mencari solusinya dengan bantuan inverse modulo M dengan cara pakai metode backwards dan juga nanti akan menggunakan algoritma Euclid.

Jadi kalau kita sudah mendapatkan inversenya, maka si inverse ini bisa kita kalikan di dalam kongruensi itu,

misalnya si A itu punya inverse A bar tadi,

jadi kita akan kalikan A bar kali A kali X itu kongruen dengan A bar kali B modulo M,

Jadi sekarang langkah yang kita lakukan pertama adalah mencari si inverse A nya dulu,

Kalau kita sudah ketemu si A bar tadi akan ditaruh di sisi kiri maupun sisi kanan,

maka X nya itu akan kongruen dengan A bar B modulo M dan itu merupakan solusinya.

Teoremanya itu merangkum sifat yang tadi sudah kita bahas,

jadi jika A dan M relatif prima dan M nya lebih besar 1,

maka akan terdapat A bar sedemikian sehingga A bar di kali A kongruen 1 modulo M.

Jadi selain merangkum bahwa si A bar itu merupakan inverse,

teorema ini menjelaskan kapan kita punya inverse.

jadi sekarang kita punya kongruennya itu kan berarti 1 modulo 4.

Sekarang kalau kita punya di sebelah kirinya itu X nya kita ambil 1,

maka inversenya adalah 1 karena 1 kali 1 itu kongruen dengan 1 modulo 4.

maka si inversenya juga akan sama dengan 3 karena 3 kali 3 itu nanti akan kongruen 1 modulo 4.

kita tidak bisa mencari nilai berapapun sedemikian

sehingga 2 dikali sesuatu atau sesuatu kali 2 itu kongruen dengan 1 modulo 4.

Sehingga kita sebut si X sama dengan 2 ini tidak punya inverse.

Karena dia modulo 4 kan bilangannya 0, 1, 2, 3 atau 1, 2, 3, 4 tergantung rujukan yang kita pakai.

Nah 0 atau 4 modulo 4 itu tidak akan ada inversenya untuk modulo berapapun,

jadi biasanya yang dicari inversenya itu adalah elemen yang tidak 0.

Kenapa si X sama dengan 2 ini tidak punya inverse?

Karena tadi jaminan bahwa dia mempunyai inverse adalah A dan M itu relatif prima,

sedangkan di sini 2 sama 4 itu tidak relatif prima.

Kalau X sama dengan 3 itu punya inverse karena 3 sama 4 itu relatif prima.

Kita tahu A dan M itu relatif prima, artinya apa?

Dengan demikian kita bisa mencari bilangan bulat S dan T sehingga kita bisa menuliskan SA ditambah TM itu sama dengan 1.

Artinya SA plus TM itu adalah kongruen dengan 1 modulo M.

TM karena dia kelipatan dari M maka dia akan kongruen dengan 0 modulo M.

Sehingga yang di sisi kiri tinggal si SA.

TMnya tadi 0 jadi SA ditambah 0 itu akan sama dengan SA.

Jadi dari kongruen linear ini kita akan melihat bahwa si S tadi itu akan merupakan inverse perkalian untuk A modulo M.

Sekarang kalau kita lihat inverse-nya itu bisa unik atau tidak unik.

Ini nanti kita bisa tunjukkan bahwa si inverse-nya ini akan unik kalau terhadap modulo M.

Jadi nanti bisa dicoba kalau kita punya inverse yang berbeda misalnya T.

TA itu kongruen 1 modulo M nanti kita bisa buktikan dengan persamaannya nanti Snya itu akan sama dengan T.