INSTITUT PERTANIAN BOGOR FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM Jl. Meranti, Kampus IPB Dramaga, Telp./Fax 0251-8625481/8625708 Email:
[email protected], https://www.fmipa.ipb.ac.id
Pertemuan 4 Pengantar Teori Bilangan Pembinaan OSN SMA/SMK EFARINA Kabupaten Simalungun
2016
Bilangan Prima, FPB, KPK dan Faktorisasi Prima
• Bilangan prima memiliki banyak peranan dalam bidang ilmu komputer, terutama di bidang keamanan informasi. Bilangan prima adalah bilangan bulat positif p > 1 sedemikian sehingga pembagi bilangan tersebut hanya ada tepat 2, yaitu 1 dan p 2
Bilangan Prima, FPB, KPK dan Faktorisasi Prima • Jika suatu bilangan yang lebih besar dari satu bukan bilangan prima, bilangan itu disebut bilangan komposit. • Teorema : (Topik Erotosthenes): Untuk setiap bilangan komposit n ada bilangan prima p sehingga p|n dan p
3
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Ada 2 Cara paling umum mengecek Bilangan Prima: • Teknik Sieve of Eratosthenes (dengan menggunakan Tabel) • Cara lain untuk menguji apakah n merupakan bilangan prima atau komposit, kita cukup membagi n dengan sejumlah bilangan prima, mulai dari 2, 3, … , bilangan prima n. Jika n habis dibagi dengan salah satu dari bilangan prima tersebut, maka n adalah bilangan komposit, tetapi jika n tidak habis dibagi oleh semua bilangan prima tersebut, maka n adalah bilangan prima
4
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Teknik Sieve of Eratosthenes (dengan menggunakan Tabel) • Buatlah tabel yang berisi bilangan bulat positif berurutan dari 2 hingga n. • Misal p adalah sebuah bilangan bulat yang nilai awalnya ialah 2, yaitu bilangan prima pertama. • Mulai dari p tandai bilangan bulat kelipatan dari p (2p, 3p, …) selain p yang ada pada tabel. • Kemudian, carilah ganti nilai p dengan nilai terkecil pertama yang lebih besar dari p yang tidak ditandai pada tabel. Jika tidak ada bilangan demikian, maka langkah dihentikan. Jika ada, maka kembali ke langkah ketiga. • Bilangan prima yang diperoleh adalah nilai yang tidak ditandai pada tabel.
5
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Faktor Persekutuan Terbesar (FPB) • FPB dari dua buah bilangan a dan b ialah bilangan d terbesar sedemikian sehingga d merupakan pembagi dari a sekaligus pembagi dari b ( d | a dan d | b ). Apabila untuk dua bilagan bulat sembarang a dan b sedemikian sehingga FPB(a, b) = 1, kedua bilangan tersebut dikatakan saling prima 6
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Faktor Persekutuan Terbesar (FPB) • Contoh Berapa FPB dari 45 dan 36?
7
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Faktor Persekutuan Terbesar (FPB) • Metode Euclid (Algoritma Euclidean) 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 ulang kembali ke langkah 1. • Contoh: m = 80, n = 12 dan dipenuhi syarat m n 8
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Faktor Persekutuan Terbesar (FPB) • Bezout’s Theorem Jika d = gcd(a,b) maka ada x dan y bulat s.r.s, z=ax+by, jika dan hanya jika gcd(a,b) | z Contoh: Jika 3 adalah FPB dari 21 dan 12 (FPB(21,12)=3), s.r.s, 3=21x +12y; Dari 3 = FPB(21,12), didapatkan hasilnya adalah: 3 = 21*(3) + 12*(-5) sehingga untuk x= 3 dan y= -5. 9
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Relatif Prima • Dua buah bilangan bulat a dan b dikatakan relatif prima jika FPB(a, b) = 1 • Contoh - Apakah 20, dan 3 relative prima? - Apakah 20, dan 5 relative prima?
10
Bilangan Prima, FPB, KPK dan Faktorisasi Prima KPK • KPK(A, B) adalah sebuah bilangan bulat terkecil M sedemikian sehingga A merupakan pembagi dari M dan B merupakan pembagi dari M ( A|M dan B|M). KPK dapat dicari dengan menggunakan formula berikut: • KPK(A, B) =
𝑨𝑩 𝑭𝑷𝑩(𝑨,𝑩)
11
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Faktorisasi Prima • Setiap bilangan bulat positif n > 1 dapat dinyatakan secara unik sebagai: 𝛼𝑘 𝛼1 𝛼2 n = 𝑝1 𝑝2 … 𝑝𝑘 Dengan 𝑝𝑖 adalah bilangan prima ke-i dan 𝑝𝑘 adalah bilangan prima terbesar yang membagi n. Nilai 𝛼1 ≥ 0. Sebagai contoh: 1000 = 233053 3528 = 23325072 12
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Faktorisasi Prima • Contoh: Tentukan KPK dari 58 dan 106 menggunakan Faktorisasi Prima
13
Bilangan Prima, FPB, KPK dan Faktorisasi Prima Kerjakan Latihan soal bernomor Ganjil pada modul Anda!
14
KEMENTERIAN PENDIDIKAN DAN KEBUDAYAAN
INSTITUT PERTANIAN BOGOR
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM Jl. Meranti, Kampus IPB Dramaga, Telp./Fax 0251-8625481/8625708 Email:
[email protected], https://www.fmipa.ipb.ac.id
Sampai bertemu esok hari… ^_^
SELESAI
15
