Manusia itu seperti pensil… Pensil setiap hari diraut sehingga yang tersisa tinggal catatan yang dituliskannya…. Manusia setiap hari diraut oleh rautan umur hingga habis, dan yang tersisa tinggal catatan amal dan ilmunya…
Integer_lanjutan
Pembagi Bersama terBesar (PBB) = FPB = gcd (greatest common divisor) : Dua buah bilangan bulat bisa memiliki faktor pembagi yang sama, dan yang terpenting adalah faktor pembagi bersama terbesar Definisi : Misal a dan b adalah dua bilangan bulat tidak nol, PBB dari a dan b adalah bilangan bulat d sedemikian hingga d|a dan d|b.
PBB • Sifat PBB : (a) Jika c adalah PBB dari a dan b, maka c|(a+b) (b) Jika c adalah PBB dari a dan b, maka c|(a-b) (c) Jika c|a, maka c|ab
PBB • Teorema : Misalkan m dan n adalah dua bilangan bulat dengan syarat n>0 sedemikian hingga : m = n.q + r , 0≤r
PBB • Contoh : 80 = 12.6 + 8 PBB (80,12) = 4 12 = 8.1 + 4 PBB(12,8) = 4 8 = 4.1 + 4 PBB (8,4) = 4 4 = 4.1 + 0 PBB (4,4) = 4 4 = 0.c + 4 PBB (4,0) = 4 Diperoleh : PBB(80,12) = PBB(12,8) = PBB( 8,4) = PBB(4,0) = 4
Algoritma Euclidian • Sebelumnya mencari PBB : mendaftar semua pembagi masing-masing bilangan bulat, lalu memilih yang terbesar. • Metode lain yang lebih efektif (mangkus) : algoritma euclidian :
Algoritma Euclidian Misal m dan n adalah bil bulat tak negatif dengan m≥n. Misalkan r0 = m dan r1 = n, lakukan secara berturutturut pembagian seperti pada teorema PBB untuk memperoleh : r0 = r1.q1 + r2 r1 = r2.q2 + r3 dst rn-2 = rn-1.qn-1 + rn rn-1 = rn.qn + 0 sehingga : PBB(m,n)=PBB(r0,r1)=PBB(r1,r2)=…= PBB(rn2,rn-1)=PBB(rn-1,rn)=PBB(rn,0)=rn
Algoritma Euclidian Jadi, PBB dari m dan n (m≥n) adalah sisa terakhir yang tidak nol dari runtutan pembagian tersebut. ALGORITMA : 1. Jika n = 0 maka m adalah PBB(m,n); stop. tetapi jika n≠0, lanjutkan ke langkah 2
2. Bagilah m dengan n dan misalkan r adalah sisanya 3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulangi kembali langkah 1
Algoritma Euclidian • Contoh : tentukan PBB dari 90 dan 16 dengan menggunakan algoritma euclidian
ALGORITMA EUCLIDIAN • Pseudo code procedure euclidian (input m, n : integer, output PBB : integer) {mencari PBB (m,n) dengan syarat m dan n bilangan tak negatif dan m≥n} Deklarasi r : integer Algoritma : while n≠0 do r m mod n m n n r endwhile {n=0, maka PBB (m,n) = m} PBB m
Kombinasi Lanjar Misal a dan b adalah dua buah bilangan bulat positif, maka terdapat bilangan bulat m dan n sedemikian hingga PBB(m,n) = am + bn Jadi PBB dua bilangan bulat m dan n dapat dinyatakan sebagai kombinasi lanjar (linear combination) dengan a dan b sebagai koefisien-koefisiennya. Misal : PBB(80,12) = 4 dan 4 = -1.80+7.12,, disini a = -1, b = 7 Metode : sama dengan algoritma euclidian (dalam menghitung PBB), melakukan pembagian secara mundur
Kombinasi Lanjar • Contoh : Nyatakan PBB(312,70) = 2 sebagai kombinasi lanjar dari 312 dan 70 Jawab : Terapkan algoritma euclidian untuk memperoleh PBB(312,70) = 2 312 = 70.4 + 32 (i) 70 = 32.2 + 6 (ii) 32 = 6.5 + 2 (iii) 6 = 2.3 + 0 (iv) PBB = 2
Kombinasi Lanjar Susun (iii) menjadi 2 = 32 – 5.6 (v) Susun (ii) menjadi 6 = 70 – 2.32 (vi) Sulih (substitusi) (vi) ke dalam (v) 2 = 32 – 5.(70-2.32)= 1.32 – 5.70 + 10.32 = 11.32 – 5.70 (vii) Susun (i) menjadi 32 = 312 – 4.70 (viii) Sulih (viii) ke dalam (vii) 2 = 11.32 – 5.70 = 11(312 – 4.70) – 5.70 = 11.312 – 44.70 – 5.70 = 11.32 – 49.70 Jadi PBB(312,70) = 2 = 11.32 – 49.70 {a = 11, b = -49}
Aritmetika Modulo • Peran penting pada komputasi integer, khususnya kriptografi • Operator : mod • m mod n = r sedemikian hingga m = nq + r • Jika m mod n = 0, maka m merupakan kelipatan dari n
KOngruen • a ≡ b (mod n) {a kongruen dengan b dalam modulo n} • a dan b dikatakan konruen dalam modulo n jika a dan b memiliki sisa yang sama jika dibagi n • a ≡ b (mod n) jika n habis membagi a – b atau bisa dituliskan dalam hubungan a = b + kn { a dan b bil bulat, n > 0, k bil bulat}
Relatif Prima • PBB(m,n) = 1 m dan n relatif prima • Jika m dan n relatif prima, maka menurut teorema kombinasi lanjar kita dapat menemukan bilangan bulat a, b sedemikian hingga am + bn = 1 • Contoh : 2.20 + (-13).3 = 1
Inversi Modulo • Jika m dan n relatif prima, dan n > 1, maka didapatkan inversi dari m modulo n adalah bilangan bulat mꜚ sedemikian hingga : m.mꜚ ≡ 1 (mod n) • Pembuktian : PBB(m,n) = 1 {relatif prima} am + bn = 1 hal ini mengimplikasikan : am + bn ≡ 1 (mod n) karena bn ≡ 0 (mod n), maka am ≡ 1 (mod n) kekongruenan ini berarti bahwa a adalah inversi dari m modulo n So : untuk mencari invers : dibuat kombinasi lanjar , koefisien dari kombinasi lanjar tsb merupakan inversnya
Inversi modulo • Latihan : Tentukan inversi modulo dari 4(mod 9), 17(mod 7), dan 18(mod 10)
Inversi modulo • Metode lain menghitung invers mod : Persamaan berikut a.aꜚ ≡ 1 (mod m) Bisa ditulis dalam hubungan a.aꜚ = 1 + km
Kekongruenan Lanjar • Adalah kongruen yang berbentuk ax ≡ b (mod m)
