Matematika Diskrit : Konsep Keterbagian, Modulo, Bilangan Prima, Algoritma Euclidean ,dan Contoh Soal
Keterbagian
Definisi
Jika a dan b adalah bilangan bulat, a dikatakan membagi b jika terdapat bilangan bulat c di mana b = ac. a membagi b dinotasikan a|b, dan a tidak membagi b dinotasikan a | b dimana garis tegak lurus dicoret.
Contoh :
- 5 membagi 10
- 3 membagi 6
- 2 tidak membagi 9
Teorema
Contoh :
- 2|6 dan 2|4 maka 2|10
- 5 | 15 maka 5|60
- 7 | 21 dan 21|42 maka 7|42
Latihan 1
Tentukan apakah a | b jika
- a = 3, b = 10
- a = 19, b = 95
Kerjakan soal-soal berikut menggunakan teorema yang telah dijelaskan.
- Jika 8 | 32 dan 8 | 64, apakah 8 |96?
- Jika 16 | 80, apakah 16|240?
- Jika 8|24 dan 24|72, apakah 8|72?
Konsep modulo
Teorema
dimana
- a = dividend
- d = divisor / pembagi
- q = quotient
- r = remainder/sisa
Contoh :
- 10 = 4.2 + 2
- 90 = 7.12 + 6
- 25 = 6.4 +1
Latihan 2
Tuliskan dalam bentuk a = d.q + r, dengan
- a = 91, d = 36
- a = 65, d = 12
- a = 121, d = 10
Quotient dan remainder dapat dituliskan sebagai berikut:
r = a mod d
Contoh :
- 2 = 5 mod 3
- 1 = 10 mod 3
- 15 = 35 mod 20
Aritmatika modular
Teorema I
dimana
≡ congruent
Contoh :
- 5 ≡ 15 (mod 10)
- 6 ≡ 21 (mod 15)
Teorema II
Contoh :
Jika 2 ≡ 5 (mod 3) dan 1 ≡ 4 (mod 3), maka 3 ≡ 9 (mod 3) dan 2 ≡ 20 (mod 3)
Teorema Corollary
Contoh :
- 123 mod 11 = ((100 mod 11) + (23 mod 11)) mod 11
- 450 mod 21 = ((90 mod 21)(5 mod 21)) mod 21
Bilangan prima
Definisi
Suatu bilangan bulat yang lebih dari 1 dikatakan prima jika dan hanya jika hanya memiliki faktor 1 dan dirinya sendiri. Bilangan bulat yang lebih dari 1 dan bukan prima disebut bilangan komposit.
Pengujian keprimaan
Teorema
Jika n adalah bilangan komposit, maka n memiliki faktor prima yang kurang dari dan sama dengan √n
Contoh 1 :
Karena n = 21 adalah bilangan komposit, maka n memiliki faktor prima 3 ( kurang dari sama dengan √21 = 4.6).
Jika n tidak memiliki faktor prima yang kurang dari sama dengan √n, maka n adalah bilangan prima
Contoh 2 :
Karena n = 19 tidak memiliki faktor prima, maka n adalah bilangan prima
Faktor Persekutuan Terbesar (GCD)
Definisi
Diberikan bilangan bulat tidak nol a dan b. Bilangan bulat terbesar d di mana d|a dan d|b disebut faktor pembagi bersama terbesar (FPB/GCD) dari a dan b.
Contoh
- 3 adalah FPB(6,9)
- 12 adalah FPB(24,36)
Relatif Prima
Definisi
Contoh
- 5 dan 7 adalah relatif prima
- 12 dan 25 adalah relatif prima
Algoritma Euclidean
Misalkan akan ditentukan FPB(a,b), a > b.
- Tuliskan a dan b dalam bentuk a = b.q +r
- Substitusi nilai a = b dan b = r
- Ulangi langkah 1, sampai r bernilai 0
- FPB = b
Contoh :
Posting Komentar