Matematika Diskrit - Pertemuan 7
Matematika Diskrit - Pertemuan 7
Matematika Diskrit - Pertemuan 7
Fakultas : FTI
Program Studi : TEKNIK INFORMATIKA
Tatap Muka
Deskrispsi Tugas -
Kontrak 10 % : Kehadiran
Perkuliahan 40 % : Tugas
25 % : UTS
25 % : UAS
1. Bilangan Bulat
Dua buah bilangan bulat dapat memiliki faktor pembagi yang sama. Faktor
pembagi bersama yang terpenting adalah faktor pembagi bersama terbesar atau
PBB. Misalnya 45 memiliki faktor pembagi 1, 3, 5, 9, 15, dan 45 sendiri. Sedangkan
46 memiliki faktor pembagi 1, 2, 3, 4, 9, 12, 18 dan 36 sendiri. Faktor pembagi
bersama dari 45 dan 46 adalah 1, 3, 9, yang terbesar adalah 9 sehingga disimpulkan
PBB (45, 36) = 9.
Contoh :
Misalkan m dan n adlaah dua buah bilangan bulat dengan syarat n > 0 sedemikian
sehingga
Contoh :
Jika 80 dibagi dengan 12 memberikan hasil 6 dan sisa 8, atau 80 = 12.6+8. Menurut
(1)
3. Algoritma Euclidian
a. Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah
bilangan bulat.
b. Euclid, penemu algoritma Euclidean, adalah seorang matematikawan Yunani
yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal,
Element.
c. Diberikan dua buah bilangan bulat tak-negatif m dan n (m≠n). Algoritma
Euclidean berikut mencari pembagi bersama terbesar dari m dan n.
Penyelesaian :
m = 12, n = 8
12 = 1.8+4
5. Langkah instruksi 3 :
m = 8, n = 4
8 = 2.4 + 0
7. Langkah instruksi 3 :
m = 4, n = 0
Misalkan a dan b adalah dua buah bilangan bulat positif, maka terdapat bilangan
bulat m dan n sedemikian sehingga PBB (a, b) = ma + nb
PBB dua buah bilangan bulat a dan b dapat dinyatakan sebagai kombinasi lanjar
dengan m dan n sebagai koefisien-koefisien. Misalnya PBB (80, 12) = 4, dan 4 =
(-1). 80+7.12 dimana m = -1 dan n = 7
Contoh :
Nyatakan PBB (312, 70) = 2 sebagai kombinasi lanjar dari 312 dan 70
Penyelesaian :
312 = 4. 70 + 32 … (1)
70 = 2. 32 + 6 … (2)
32 = 5. 6 + 2 …(3)
6 = 3. 2 + 0 …(4)
2 = 32 − 5. 6 …(5)
6 = 70 − 2. 32 …(6)
32 = 312 − 4. 70 … (8)
4. Aritmatika Modulo
Contoh :
5. Modulo Kongruen
Kadang dua buah bilangan bulat, a dan b mempunyai sisa yang sama jika dibagi
dengan bilangan bulat positif m. katakan bahwa a dan b kongruen dalam modulo
m, dan dilambangkan sebagai :
𝑎≡𝑏 (𝑚𝑜𝑑 𝑚)
≡𝑘𝑜𝑛𝑔𝑟𝑢𝑒𝑛
𝑎≡/𝑏 (𝑚𝑜𝑑 𝑚)
Contoh :
𝑎 = 𝑏 + 𝑘𝑚
Pembuktian inversi modulo ini sangat mudah. Tentang relatif prima diketahui
bahwa PBB (a, m) = 1. Terdapat bilangan bilangan bulat p dan q sedemikian
sehingga
𝑝𝑎 + 𝑞𝑚≡1
𝑝𝑎 + 𝑞𝑚≡1 (𝑚𝑜𝑑 𝑚)
𝑝𝑎 ≡1 (𝑚𝑜𝑑 𝑚)
Contoh :
Tentukan inversi dari 4 (𝑚𝑜𝑑 9), 17 (𝑚𝑜𝑑 7), 𝑑𝑎𝑛 18 (mod 10)
Penyelesaian :
a. Karena PBB (4, 9) = 1, maka inversi dari 4 (mod 9) ada. Dari algoritma
eucledian diperoleh bahwa
9 = 2.4+1
Susun persamaan diatas menajdi
1 = 7 − 2. 3 … (4)
𝑠𝑢𝑠𝑢𝑛 (1)𝑚𝑒𝑛𝑗𝑎𝑑𝑖 :
3 = 17 − 2. 7 … (5)
𝑠𝑢𝑙𝑖ℎ𝑘𝑎𝑛 5 𝑘𝑒 𝑑𝑎𝑙𝑎𝑚 4
1 = 7 − 2. (17 − 2. 7) = 1. 7 − 2. 17 + 4. 7 = 5. 7 − 2. 17
Atau
− 2. 17 + 5. 7 = 1
7. Kekongruenan Lanjar
Kekongruenan lanjar adalah kongruen yang berbentu
𝑎𝑥≡𝑏(𝑚𝑜𝑑 𝑚)
m = bilangan positif
x = peubah
3+𝑘.4
𝑥= 2
4𝑥 = 12
1 1
4
. 4𝑥 = 4
. 12 𝑥 = 3
Bibliografi
Salamah, Ummy Gusti, and Anindya Ananda Hapsari. Matematika Diskrit. Media
Sains Indonesia, 2021.
Nengsih, Yeyi Gusla, S. Kom, and M. Kom. MATEMATIKA DISKRIT. Jakad Media
Publishing, 2020.