TEORI BILANGAN

TEORI BILANGAN

-Teori bilangan (number theory) adalah teori yang mendasar dalam memahami algoritma kriptografi

-Bilangan yang dimaksudkan adalah bilangan bulat (integer)

Sifat Pembagian pada Bilangan Bulat

-Misalkan a dan b adalah dua buah bilangan bulat dengan syarat a ¹ 0. Kita menyatakan bahwa a habis membagi b (a divides b) jika terdapat bilangan bulat c  sedemikian sehingga b = ac.

-Notasi: a | b  jika b = ac, c Î Z dan a ¹ 0. (Z = himpunan bilangan bulat)

-Kadang-kadang pernyataan “a habis membagi b“ ditulis juga  “b  kelipatan a”.

-Contoh 1: 4 | 12 karena 124 = 3 (bilangan bulat) atau 12 = 4 ´ 3. Tetapi 4 | 13 karena 134 = 3.25 (bukan bilangan bulat).

TEOREMA I ( Teorema Euclidean)

Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n>0. Jika m dibagi dengan n maka terdapat 2 buah bilangan bulat unik q (quotient) dan r (reainder), sedemikian hingga

m = nq + r

 

q= hasil bagi

r = sisa (perhatian : r nilainya harus positif)

dengan 0£ r

Contoh  Soal:

a.     1988 dibagi dengan 97  memberikan hasil bagi 20 dan sisa 48

1988 = 97.20 + 47

b.     -52 dibagi dengan 3 memberikan hasil bagi -18 dan sisa 2

-52 = 3 (-18) + 2

Pembagi Bersama Terbesar (PBB)

-Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar (PBB – greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini kita nyatakan bahwa PBB(a, b) = d.

Contoh 3.

Faktor pembagi 40: 1, 2, 4, 5, 8, 10

Faktor pembagi 32: 1, 2, 4, 8

Faktor pembagi bersama dari 40 dan 32 adalah 1, 2, 4,8

PBB(45, 36) = 8 

TEOREMA 2

Misalkan m dan n adalah dua bilangan bulat dengan syarat n >0 sedemikian sehingga

M = nq + r , 0 lebih dari atau sama dengan nol r

maka PBB (m,n) = PBB (n, r)

Contoh :

1. m = 69, n = 16

68 = 16. 4 +5

maka PBB (68, 16) = PBB (16, 4)= 4

2. m = 73 ; n =x , m dibagi n dituliskan dalam bentuk

m= nq +r; r = 3 

73= 10.7 + 3

PBB (73, 10)= PBB (10, 3) = 3

Oke, sekian dulu postingan dari saya, masih ada lanjutannya di Algoritma Euclidean. Silahkan jawab kuis dibawah ini :

 KUIS:

1. 2001 dibagi dengan 30 memberikan hasil bagi 66 dan sisa 21

2. Berapa PBB dari m = 62, n = 18

3.Berapa PBB dari m = 89 , n = x , dan r = 2

Tulis jawabanmu di kotak komentar ya..

QUOTE MANIS BUAT KAMU :

Untuk melihat dunia yang sesungguhnya, kita perlu membuka wawasan seluas-luasnya