Matematika Diskrit : Konsep Keterbagian, Modulo, Bilangan Prima, Algoritma Euclidean ,Dan Pola Soal

Matematika Diskrit : Konsep Keterbagian, Modulo, Bilangan Prima, Algoritma Euclidean ,dan Contoh Soal

Keterbagian

Definisi 

Jika a dan b yaitu bilangan bulat, a dikatakan membagi b jikalau terdapat bilangan lingkaran 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 memakai 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 

1. a = 91, d = 36 
2. a = 65, d = 12 
3. a = 121, d = 10

Quotient dan remainder sanggup 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 lingkaran yang lebih dari 1 dikatakan prima jikalau dan hanya jikalau hanya mempunyai faktor 1 dan dirinya sendiri. Bilangan lingkaran yang lebih dari 1 dan bukan prima disebut bilangan komposit.

Pengujian keprimaan

Teorema 

Jika n yaitu bilangan komposit, maka n mempunyai faktor prima yang kurang dari dan sama dengan √n

Contoh 1 : 

Karena n = 21 yaitu bilangan komposit, maka n mempunyai faktor prima 3 ( kurang dari sama dengan  √21 = 4.6).

Jika n tidak mempunyai faktor prima yang kurang dari sama dengan √n, maka n yaitu bilangan prima 

Contoh 2 : 

Karena n = 19 tidak mempunyai faktor prima, maka n yaitu bilangan prima 

Faktor Persekutuan Terbesar (GCD)

Definisi 

Diberikan bilangan lingkaran tidak nol a dan b. Bilangan lingkaran terbesar d di mana d|a dan d|b disebut faktor pembagi bersama terbesar (FPB/GCD) dari a dan b.

Contoh 

• 3 yaitu FPB(6,9) 
• 12 yaitu FPB(24,36)

Relatif Prima

Definisi

Contoh

• 5 dan 7 yaitu relatif prima 
• 12 dan 25 yaitu relatif prima 

Algoritma Euclidean

Misalkan akan ditentukan FPB(a,b), a > b.

1. Tuliskan a dan b dalam bentuk a = b.q +r
2. Substitusi nilai a = b dan b = r
3. Ulangi langkah 1, hingga r bernilai 0
4. FPB = b

Contoh :

Sumber http://wikiwoh.blogspot.com