BAHAN AJAR TEORI BILANGAN

BAHAN AJAR TEORI BILANGAN

PENYUSUN NURYADI, S.PD.SI, M.PD.

PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MERCU BUANA YOGYAKARTA 2014

Pendidikan Matematika FKIP UMB-Yogyakarta

Page 1

KETERBAGIAN DAN REPRESENTASI BILANGAN BULAT A. BILANGAN BULAT Definisi bilangan bulat : Bilangan yang anggota-anggota terdiri dari {…….,-1, 0, 1,2,………..}

1. Definisi urutan dalam bilangan bulat

Untuk

berarti

atau

bilangan

bulat positif Sifat urutan dalam bilangan bulat: a. Ketertutupan pada

(bilangan bulat positif)



jumlah dari dua



hasil kali dari dua

adalah adalah

b. Hukum Trichotomy maka berlaku salah satu hubungan berikut: { Himpunan bilangan bulat dikatakan himpunan yang terurut, karena mempunyai sub.himpunan yang tertutup terhadap operasi +, x serta hukum trichotomy berlaku untuk semua sub.himpunan bilangan bulat. 2. Well Ordery Property ( Sifat Pengurutan Wajar) Setiap himpunan bilangan bulat positif

yang tidak kosong (

)mempunyai elemen terkecil, yaitu:

Contoh : 3. Teorema 1.1 : Sifat Archimedes Jika a dan b sembarang bilangan bulat positif maka Bukti : Kita andaikan sifat archimedes salah, yaitu Bentuk himpunan Bilangan asli: Pendidikan Matematika FKIP UMB-Yogyakarta

Page 2

Karena Sehingga himpunan S terdiri atas bilangan-bilangan asli. Jadi

karena itu

menurut WOP, S dipastikan memiliki sebuah unsur terkecil sebut saja Dari aturan pembentukan himpunan S, maka tetapi

.

elemen terkecil dari S,

untuk suatu

Kontradiksi dengan b-ma elemen terkecil S. Sehingga pengandaian salah, yang benar sifat Archimedes benar. Contoh : 2.3 < 44-2.3>0…..2.3-4 >0 4. Teorema 1.2 : Prinsip Induksi Matematika Misalkan S adalah sebuah himpunan bagian dari bilangan bulat positif yang memiliki sifat : a. 1 unsur dari S b. Jika k unsur dari S maka k + 1 juga unsur dari S.

Dapat disimpulkan S adalah himpunan semua bilangan bulat positif. Bukti : Misalkan T adalah semua himpunan bilangan bulat positif yang terletak dalam S dan diasumsikan T tidak kosong. Menurut aturan WOP, T memiliki unsur terkecil, misal a. Karena 1 dalam S, tentu karena a unsur terkecil dari T maka

, juga

bukan unsur dari T.

Dengan demikian dapat disimpulkan bahwa T adalah himpunan kosong dan mengakibatkan S memuat semua bilangan bulat positif. Contoh : Buktikan bahwa formula di bawah ini berlaku setiap n bilangan bulat positif.

Bukti : Untuk n =1, diperoleh

, artinya 1 terletak dalam S

Asumsikan k dalam S, artinya berlaku Pendidikan Matematika FKIP UMB-Yogyakarta

Page 3

…………..(2) Selanjutnya akan ditunjukkan n= k +1 dalam S atau

Persamaan (2) diatas, jika kedua ruasnya ditambah

diperoleh

[

]

[

(

] )

(

)

Hal ini menunjukkan bahwa jika k dalam S maka k +1 juga dalam S, dan S memuat semua bilangan bulat positif, artinya formula tersebut benar untuk n = 1, 2, 3, …. Pembuktian dengan menggunakan teorema 1.2 ada kalanya kurang efektif. Oleh karena itu prinsip tersebut dimodifikasi menjadi seperti berikut : Misalkan S adalah sebuah himpunan bagian dari bilangan bulat positif yang memiliki sifat berikut : a. 1 unsur dari S b. Jika k suatu bilangan bulat positif, sehingga 1,2,....,k dalam S, maka k +1 juga unsur dari S

Dapat disimpulkan S adalah himpunan semua bilangan bulat positif Latihan : 1. Buktikan dengan induksi matematika berikut ini :

a. Pendidikan Matematika FKIP UMB-Yogyakarta

(

)

untuk setiap n

Page 4

Bukti : (

a.

)

(

b.

)

berlaku juga

untuk (

)

(

(

)(

))

( (

)

(

)

(

)]) ]

(

)

(

)(

*

)

+

2. Papan catur berlubang adalah papan ukuran

yang dihilangkan

sembarang satu petaknya. Buktikan papan catur ditutup oleh ubin triomino huruf “L” untuk


)

[ (

[

b.

) (

]

([

)

berlubang dapat !

Page 5

Bukti : Untuk n =1 

sehingga bentuk ubin



Untuk n = k asumsikan benar maka n = k+1 juga benar artinya papan catur juga dapat di tutup oleh ubin triomino huruf “L”

ukuran

𝑘

Gambar :

𝑘

𝑘

𝑘

(

3.

)

untuk setiap

Jawab : Pendidikan Matematika FKIP UMB-Yogyakarta

Page 6

(

maka

) (

maka

)

…..(persamaan 1) berlaku juga untuk (

)

Pada persamaan (1) ditambah ( (

)

)

(diteruskan oleh mahasiswa)

B. Keterbagian/Divisibility Definisi 1. Jika a dan b adalah bilangan bulat dengan a  0, dikatakan a membagi (habis) b jika terdapat bilangan bulat c sedemikian hinga b = ac. Bilangan a disebut pembagi atau faktor dari b dan dinotasikan a|b. Sebaliknya a tidak membagi (habis) b diberi notasi a | b. Contoh : karena Teorema 1.7. Jika a, b dan c adalah bilangan bulat dengan a| b dan b|c, maka a| c. Beri contoh: a = 3, b = 6 dan c = 12 adalah anggota bilangan bulat. Mudah dibuktikan: 3|6 karena 6|12 karena

(berdasarkan definisi 1) (berdasarkan definisi 1),

maka berdasarkan teorema 1.7 dan definisi 1 terbukti bahwa 3|12 Teorema 1.8. Jika a, b, m, dan n adalah bilangan bulat, dan jika c| a dan c|b, maka c| (ma + nb). Beri contoh (di serahkan kepada mahasiswa).


Page 7

Bukti : …..(persamaan 1) ……( persamaan 2) …… persamaan 3 Substitusikan persamaan 1 dan 2 ke persamaan 3

Karena

dan

maka

Jadi

dan

dan

.

sehingga c|(ma + nb)

Contoh : Misal

Teorema 1.9. Algoritma Pembagian. Jika a dan b adalah bilangan bulat sedemikian hingga b > 0, maka terdapat tepat satu bilangan bulat q dan r sedemikian hingga

a = bq + r dengan 0  r < b.

q= hasil bagi dari pembagian a oleh b r= sisa pembagian a oleh b Contoh : , dengan Contoh 2 : dengan Bukti. Diketahui : a,b bulat, b>0 Akan dibuktikan: terdapat dengan tunggal Maka


Page 8

Langkah pembuktian a. Dibentuk himpunan S = { abk , dengan k adalah bilangan bulat}. b. Misalkan T adalah himpunan semua bilangan bulat nonnegative yang berada di dalam S. c. Himpunan T jelas tidak kosong karena

abk

adalah positif jika k adalah

bilangan bulat dengan k < a/b. d. Berdasarkan sifat WOP himpunan T mempunyai elemen terkecil r. Misalkan r =

abq. Sesuai dengan pembentukan r jelas r  0.

e. Ditunjukkan bahwa r < b. Jika

ab(q1) 0.

abq b = abq bilangan

r > r  b =

Hal ini kontradiksi dengan pemilihan r =

bulat terkecil yang berbentuk f.

r  b,maka

abk. Jadi terbukti 0  r < b.

Langkah selanjutnya adalah menunjukkan bahwa q dan r adalah tunggal. Asumikan bahwa terdapat dua persamaan a = bq1 + r1 dan a = bq2 + r2, dengan 0  r1 < b dan 0  r1 < b. Maka

0 = b(q1  q2) + (r1  r2) r2  r1 = b(q1  q2) Ini berarti bahwa b membagi r2  r1. Karena 0  r1 < b dan 0  r2 < b, sehingga  b < r2  r1 < b. Jadi b dapat membagi r2  r1 hanya jika r2  r1 = 0 atau r1 = r2. Akibatnya diperoleh juga q1 = q2. g. Kesimpulan : Jadi terbukti ketunggalan.

Contoh. Jika a = 133 dan b = 21, maka q = 6 dan r = 7, karena 133 = 21·6 + 7. Jika a =  50 dan b = 8, maka q = 7 dan r = 6, karena  50 = 8(7) + 6. Karena pembagi q adalah bilangan bulat terbesar sedemikian hingga is the bq  a, dan r =

abq, akibatnya q = [a/b], r =

aba [ /b]

Contoh. Misalkan a = 1028 dan b = 34. Maka a = bq + r dengan 0  r < b, q = [380/75] =  6 dan Pendidikan Matematika FKIP UMB-Yogyakarta

Page 9

r =  380 [380/75]·34 = 1028  30·34 = 8. Diberikan suatu bilangan bulat d, kita dapat mengklasifikasikan bilangan bulat berdasarkan sisanya jika dibagi bilangan tersebut dibagi dengan d. Definisi. Jika sisa dari n dibagi 2 adalah 0, maka n = 2k untuk suatu bilangan bulat positif k, dan n disebut bilangan genap, sementara itu jika sisa n dibagi 2 adalah 1, maka n = 2k + 1 untuk suatu bilangan bulat k, dan n disebut bilangan ganjil. Klasifikasikan bilangan bulat untuk nilai d = 3.. Misal :

.

Bentuk himpunan Maka Untuk

Buktikan ! a. Kuadrat bilangan ganjil berbentuk 4k+1

= Misalkan

jadi ………(1)

b. Kuadrat bilangan ganjil berbentuk 8k+1 Karena pada persamaan 1 terbukti

ganjil, maka untuk membuktikan

8k+1 juga ganjil menggunakan bilangan dasar ganjil 4k+1


Page 10

Misalkan :

Latihan :

1. Tunjukkan bahwa 3 habis membagi a3 - a untuk setiap bilangan bulat a. Bukti : Misalkan ada a Є Z akan dibuktikan bahwa 3 │ a3 - a a3 - a = a (a – 1) (a + 1) Kita melihat bahwa a = 3b + r, untuk suatu b Є Z dan 0 ≤ r ≤ 2. Karena nilai r (residu) dari pembagian a adalah 0 ≤ r ≤ 2, maka a menjadi tiga kemungkinan: 1. a = 3b (disubstitusikan kedalam persamaan diatas, sehingga a3 - a = 3b (3b – 1) (3b + 1) sehingga 3 │ a3 - a ..……….……………. (1) 2. a = 3b + 1, sehingga a3 - a = 3b (3b + 1) (3b + 2) sehingga 3 │ a3 – a .………………….…… (2) 3. a = 3b + 2 Untuk a = 3b + 2 diperoleh a3 - a = (3b + 1) (3b + 2) (3b + 3) = (3b + 1) (3b + 2) 3 (b + 1) sehingga 3 │ a3 – a ...….………………………………………………... (3) Dari (1) , (2) dan (3) dapat disimpulkan bahwa 3 │ a3 – a. 2. Misalkan a bilangan bulat dengan a ≥ 1. Tunjukkan bahwa

( (

))

adalah

sebuah bilangan bulat. (Hint : menggunakan teorema 1.9. algoritma pembagian) Jawab :

Kita substitusikan masing-masing nilai a ke persamaan

(

) [


(

( (

))

) ]

Page 11

C.

Representasi Bilangan Bulat Perhatikan bahwa : 34765 = 3·104 + 4·103 + 7·102 + 6·101 + 5·100 menggunakan basis 10. Secara umum bilangan yang dikenal dan banyak digunakan menggunakan basis 10, tetapi sebenarnya setiap bilangan bulat positif lebih besar dari 1 dapat digunakan sebagai basis. Teorema 1.10. Misalkan b bilangan bulat positif dengan b > 1, maka setiap bilangan bulat positif

dapat dituliskan dengan tepat

k k1 n ab k ak1b  ab 1 a0 ,

satu ekspansi

(1)

dengan k bilangan bulat tak negatif, aj adalah bilangan bulat sedemikian hingga

0aj b1 untuk

j = 0,1,…, k dan koefisien ak  0

Bukti. Bagi n dengan b ditulis

n bq0 a0,

0a0 b1

Jika q0 0, bagi q0 dengan b,

q0 bq1 a1,

0a1 b1

Proses kemudian dilanjutkan secara bertahap sebagai berikut

q1 bq2 a2, q2 bq3 a3,

0a2 b1 0a3 b1

.;

qk2 bqk1 ak1, 0ak1 b1 qk1 b0ak , 0ak b1 Jelas bahwa

n q0 q1  0 Secara berurutan substitusikan q0,q1,...,qk1, sehingga didapatkan k k1 n ab k ak1b  ab 1 a0


Page 12

Untuk membuktikan ketunggalan dari pernyataan (1), diasumsikan terdapat dua ekspansi yang nilainya sama dengan n k k1 k k1 n ab k ak1b  ab 1 a0 ckb ck1b  cb 1 c0

Kurangkan ekspansi yang satu dari yang lain, sehingga

(ak ck )bk (ak1 ck1)bk1  (a1 c1)b(a0 c0) 0 Jika dua ekspansi berbeda, maka terdapat bilangan bulat terkecil j, 0  j  k, sedemikian hingg aj  cj. Jadi

bj (ak ck )bkj (ak1 ck1)bkj1  (aj cj ) 0 (ak ck )bkj (ak1 ck1)bkj1  (aj cj ) = 0

aj cj b(ak ck )bkj1 (ak1 ck1)bkj2  (aj1 cj1) Atau dapat dituliskan

b|(aj cj ) Karena

0aj bdan 0cj b, so baj cj b. Juga karena b|(aj cj )

maka aj

cj . Hal ini kontradiksi aj  cj. Jadi ekspansi

n tunggal.

Akibat 1.10.1 Setiap bilangan bulat positif dapat direpresentasikan sebagai jumlah pangkat dari bilangan 2 yang berbeda Bukti: Notasi. Bilangan bulat positif b disebut basis. Basis 10 disebut desimal. Ekspansi basis 2 disebut ekspansi biner Ekspansi basis 8 disebut ekspansi octal. Ekspansi basis 16 disebut heksadesimal. Koefisien aj disebut digit ekspansi. (Digit biner disebut bits (binary digits)) Notasi

k k1 (akak1 aa 1 0)b menyatakan ab k ak1b  ab 1 a0

Contoh 1.25. Pendidikan Matematika FKIP UMB-Yogyakarta

Page 13

(236)7 272 376135 Contoh 1.26. Tentukan ekspansi basis 5 dari 1864. Berdasarkan teorema 1.10 maka 5 membagi 1864

Jadi

Notasi digit untuk basis 16 adalah 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Contoh. Untuk mengkonversi . Contoh :


Page 14

FAKTOR PERSEKUTUAN TERBESAR (FPB)

Faktor persekutuan terbesar merupakan pembagi – pembagi bersama dari a dan b dengan nilai pembagi yang terbesar dari a dan b tersebut. Missal: a = 8 b = 20 8 = 1,2,4,8 20 = 1,2,4,5,10,20 Maka faktor persekutuan terbesar 8 dan 20 adalah 4 1. Jika a dan b bilangan bulat, a dan b tidak sama dengan 0 maka a dan b memiliki sejumlah terbatas factor saja. Dengan kata lain himpunan factor persekutuan dari a dan b merupakan himpunan berhingga. 2. Dari poin 1 , itu disebabkan factor-fektor persekutuan dari a dan btidak akan lebih besar dari bilangan yang terbesar di antara a dab b. 3. Setiap bilangan bulat kecuali nol selalu membagi nol, sehingga a = b = 0, maka setiap bilangan bulat merupakan factor persekutuan dari a dan b, dalam hal ini himpunan semua factor persekutuan bulat positif dari a dan b merupakan himpunan tak berhinnga Teorema : Untuk

berlaku (pembagi

1. 2. 3. 4. a|b dan b|c 5. 6. 7. Bukti : (sebagai latihan mahasiswa) Pendidikan Matematika FKIP UMB-Yogyakarta

Page 15

DEFINISI FPB: Diberikan dua bilangan bulat a dan b, bahwa a,b tidak sama dengan nol. Pembagi persekutuan terbesar a dan b adalah bilangan bulat positif d yang memenuhi : (1) (2)

Teorema : Diberikan

dengan

maka

Bukti : Bentuk Akan dibuktikan S tidak kosong. Dari asumsi

maka |a| >0

Contoh: faktor persekutuan dari 24 dan 84 adalah ± 1, ±2, ±3, ±4, ±6, ±12 sehingga ( 24,84) = 12 (15,81) = 3, (100,5) = 5, (17,25) – 1, (0,44) = 44, (-6,-15) = 3, dan (17,289) = 17 DEFINISI: a dan b dikatakan relative prima jika a dan b memiliki FPB (a,b) = 1 Contoh 5. 20 dan 3 relatif prima sebab FPB(20, 3) = 1. Begitu juga 7 dan 11 relatif prima karena FPB(7, 11) = 1. Tetapi 20 dan 5 tidak relatif prima sebab FPB(20, 5) = 5 ¹ 1. Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga Contoh 6. Bilangan 20 dan 3 adalah relatif prima karena FPB(20, 3) =1, atau dapat ditulis 2 . 20 + (–13) . 3 = 1 dengan m = 2 dan n = –13. Tetapi 20 dan 5 tidak relatif prima karena FPB(20, 5) = 5 ¹ 1 sehingga 20 dan 5 tidak dapat Pendidikan Matematika FKIP UMB-Yogyakarta

Page 16

dinyatakan dalam m . 20 +n.5=1 Contoh: (25,42) = 1, maka 25 dan 42 adalah relative prima. 25 = 1,5,25 42 = 1,2,3,6,7,14,21,…,42 TEOREMA 2.1: Jika a ,b dan c adalah bilangan bulat dengan FPB(a,b) = d, dengan i). FPB(

)=1

ii). FPB Pembuktian: i) Missal FPB(

) = e maka e ≥ 1

Akan ditunjukan e = 1 FPB(

)=e

Sehingga

dan

berarti ada bilangan bulat m sehingga berarti ada bilangan bulat n sehingga

atau atau

maka de adalah Faktor Persekutuan dari a dan b. karena d adalah FPB dari a



dan b atau

. jadi e = 1. Terbukti (

)=1

Pembuktian: ii). jika a, b, dan c adalah bilangan bulat maka kita akan menunjukan bahwa Faktor Persekutuan dari a dan b adalah sama dengan faktor persekutuan dari a + bc dan b atau jika e adalah Faktor persekutuan dari a dan b. dari teorema 1.8 terlihat bahwa e juga adalah faktor persekutuan dari a + cb dan b. Jika f adalah factor persekutuan dari a + cb dan b ( berdasarkan teorema 1.8 terlihat f membagi b. Oleh karena itu

), maka f juga adalah faktor persekutuan dari a dan )

contoh teorema 2.1: misalkan Pendidikan Matematika FKIP UMB-Yogyakarta

Page 17

maka kita harus menentukan apakah berlaku : a. FPB(

)=1

Jawab : b. FPB

jadi

dan

DEFINISI: Jika a dan b bilangan bulat, kemudian kombinasi linear dari a dan b adalah

jumlal dari bentuk ma + nb, dimana m dan n adalah

bilangan bulat Dengan kata lain bahwa factor persekutuan terbesar dari a dan b dapat dinyatakan sebagai kombinasi linear dari a dan b , yaitu ma + nb dengan m,n bilangan bulat tertentu Contoh: (-12,30) = 6 = (-12) . 2 + 30 . 1 (8,15) = 1 = 8 .2 + 15 . (-1) (8, -35) = 4 = 8 . 5 + (-36) . 1 (-6, -42) = 6 = (-6) (-8) + (-42) . 1 TEOREMA 2.2 : pembagi bersama terbesar dari bilangan bulat a dan b, dan keduanya tidak nol,adalah linear paling positif yang merupakan kombinasi linear a dan b. Pembuktian: misalkan d adalah bilang positif terkecil merupakan kombinasi linear a dan b. ( ada bilang bulat positif yang paling terkecil tersebut, dengan menggunakan 1 x a + 0 . b,dan (-1) a + 0 . b,


Page 18

dimana a ≠ 0 adalah positif property baik memesan. Karena setidaknya satu dari dua kombinasi linear Dapat ditulis: d = ma + nb…………………………………………………..1 dimana m dan n adalah bilangan bulat. Akan di tunjukan bahwa dIa dan dIb. Dengan alogaritma pembagian dari dIa: a = dq + r , dari persamaan 1 terlihat bahwa:

0≤r
r = a – dq = a – q ( ma + nb) = ( 1 – qm) a –

qnb hai ini menunjukan bahwa r integer adalah kombinasi linear a dan b. karena 0≤r≤d, dan d adalak kombinasi paling linear positif a dan b. dapat disimpulkan bahwa r = 0, dan karenanya dIa. Dalam cara yang sama, dapat ditunjukan pula bahwa dIb dari persamaan 1 , terlihat bahwa : r = a – dq ( ma + nb) = ( 1- qm) a – qnb sekarang kita dapat menunjukan bahwa d adalah pembagi umum terbesar dari a dan b. untuk cara ini kita semua perlu menunjukan bahwa setiap c pembagi umum dan harus membagi d. karena d = ma + nb, jika cIa dan cIb. Teorema 1.8 memberikan cId DEFINISI: Diberikan a1, a2,................,an bilang bulat tidak sama dengan nol. Pembagi persekutuan dari bilangan bulat terbesar yang merupakan pembagi dari semua bilangan bulat dalam himpunan. Pembagi umum terbesar dari a1,a2,…,an di notasikan denagan ( a1,a2,…,an) Conto:

( 12, 18, 30) = 6 (10, 15, 25) = 5

LEMMA 2.1: jika a1,a2,…,an adalah bilangan bulat tidak semua nol, maka (a1,a2,…,an-1,an-2,an) Pembuktia : setiap pembagi

bersama dari bilangan bulat a1,a2,…,an-1,an ini

khususnya sebuah pembagi dari an-1 dan an karena ini pembagi dari ( an-1,an) selain itu, setiap pembagi bersama dari bilangan bulat n-1, a1,a2,…,an-2, dan ( an1,an)

harus pembagi bersama semua bilangan bulat n, karena jika ia membagi (

an-1,an) , ia harus membagi kedua an-1,dan an . karena himpunan bilangan bulat n Pendidikan Matematika FKIP UMB-Yogyakarta

Page 19

dan himpunan bilangan bulat n-2 bersama dengan pembagi bersama terbesar dari duA bilangan bulat terakhir ini persis sama dengan pembagi, pembagi terbesar secara umum adalah sama. Contoh: untuk menemukan pembagi bersama terbesar dari tiga, bilangan bulat 105,140, dan 350 dengan menggunakan lemman 2.1. untuk melihat bahwa ( 105,140,350) = ( 150(140,350)) = (150,70) = 10 DEFINISI: tampak bahwa a1,a2,…an saling relative prima jika ( a1,a2,…an) = 1 . bilangan bulat ini disebut berpasangan relative prima jika untuk setiap pasangan bilangan bulat ai dan aj dan bagian ( ai-aj) = 1 , yaitu jika setiap pasangan bilangan bulat dari sebagian relative prima Sangat mudah untuk melihat jika bilangan bulat yang relative prima berpasangan, mereka harus saling relative prima. Namun, sebaliknya adalah tidak benar, sebagai contoh berikut: Contoh: bilangan bulat 15,21 dan 35 15

= 1,3,5,15

21

= 1,3,7,21

35

= 1,5,7,35

(15,21,35) = (15,(21,35)) = (15,7) =1 Terlihat bahwa tiga bilangan bulat saling relative prima , namun , setiap dua bilangan bulat ini tidak relative prima karena ( 15,21) = 3 (15,35) = 5 (21,35) =7 2.2 ALGORITMA EUCLID Lemma 2.2. Jika c dan d adalah bilangan bulat dan adalah bilangan bulat, maka

, dengan q dan r

.

Bukti: (12,4).......12=4.3 +0 sehingga bisa kita tulis (12,4)=(4,0)=4 Pendidikan Matematika FKIP UMB-Yogyakarta

Page 20

Misalkan

, maka

dan

.

Berdasar theorema 1.8

.............. (1)

Misalkan

dan

.

Berdasar theorema 1.8

Diperoleh

dan

Karena Jadi jika

. jika

dan

dan

maka

maka

.

............... (2)

Dari (1) dan (2) diperoleh:

Maka

.

Theorema 2.3. Algoritma Euclid jika dengan

dan

suatu bilangan bulat

. Jika algoritma pembagian berlaku dalam

dengan

untuk

dan

,

maka

, hasil pembagi terakhir yang tidak nol.

Diberikan theorema

, akan dicari

. Diasumsikan ,

algoritma

, menurut .

Lemma

2.2:

. Jika

maka lakukan algoritma berikut:

Cari

Jika



Page 21

Cari

. . . Jika


Cari Maka Contoh : Cari Menurut theorema algoritma pembagian

Jadi Theorema 2.4. Jika saling berurutan, dengan

dan

adalah suatu barisan Fibonacci yang yang . Maka algoritma Euclid dapat tepat n bagian dan

menunjukkan bahwa Bukti: Dengan menerapkan algoritma Euclid dan menggunakan definisi relasi bilangan Fibonacci

dalam masing-masing tahapan kita dapatkan bahwa ,


Page 22

. . .

Oleh karena itu algoritma Euclid dapat tepat n bagian dan menunjukkan bahwa

Contoh: Cari

Theorema 2.5. Theorema Lame’s. Jumlah pembagian di butuhkan untuk menentukan FPB dari dua bilangan bulat positif yang menggunakan algoritma Euclid yang tidak melebihi lima kali jumlah desimal terkecil dari dua bilangan bulat.

Bukti: Ketika kita menenrapkan algoritma Euclid untuk menemukan FPB dari dan

dengan

, kita dapat memperoleh urutan persamaan berikut:

. Pendidikan Matematika FKIP UMB-Yogyakarta

Page 23

. .

Kita menggunakan n pembagian, dengan

dan

,

sehingga: , , , , . . . ,

Sehingga

Seperti contoh 1.16 didapatkan ;

(

√ )

Jika b memiliki k digit desimal maka

dan

,

sehingga

, karena k adalah bilangan bulat maka disimpulkan


Page 24

TUGAS 1. BUKTIKAN TEOREMA DI BAWAH INI : a. diberikan

dan

b. diberikan

dimana

,

dengan k > 0, maka

dan

,

, maka

{

2. carilah x dan y yang memenuhi: a. gcd (34709, 100313)=34709 x + 100313 y b. gcd (666, 1414) = 666 x + 1414 y jawab : c. gcd (12378, 3054) = 12378 x + 3054 y 3. carilah nilai

yang mungkin jika gcd (a,b) membentuk barisan

fibonacci (minimal 3 pasang)


Page 25

KELIPATAN PERSEKUTUAN KECIL (KPK) Di Sekolah Dasar dan SMP, kita telah mempelajari Kelipatan Persekutuan Kecil (KPK).

Misalnya,

kelipatan

bilangan

bulat

positif

dari

3

adalah

3,6,9,12,15,18,….dan kelipatan dari 4 adalah 4,8,12,16,20,……. Maka kelipatan persekutuan dari 3 dan 4 adalah 12,24,36,48,…… Definisi 2.4. misalkan a dan b adalah bilangan-bilangan bulat dan m adalah kelipatan persekutuan dari a dan b jika dan hanya jika

dan

.

Secara formal, KPK dari dua bilangan bulat didefinisikan sebagai berikut : Definisi 2.5 Kelipatan Persekutuan Kecil (KPK) dari dua bilangan bulat tidak nol. a dan b adalah suatu bilangan bulat positif m ditulis [

]

, apabila

memenuhi : (i) (ii)

dan Jika

dan

maka

Dalam definisi ini dapat dimengerti bahwa kelipatan dari setiap dua bilangan bulat yang tidak nol selalu merupakan suatu bilangan bulat positif. Dalam definisi (i) mengatakan bahwa masing-masing dari dua bilangan itu membagi kelipatan persekutuan terkecilnya. Sedangkan (ii) mengatakan bahwa kelipatan persekutuan lainnya tidak lebih kecil dari KPK dari dua bilangan itu. Contoh : [

]

maka

dan

.

Kelipatan persekutuan lain, misal 48, 72, 96,….masing-masing lebih besar dari 24. Teorema 2.12 Jika c adalah suatu kelipatan persekutuan dari dua bilangan bulat yang tidak nol a dan b, maka KPK dari a dan b membagi c, yaitu [

] .

Bukti :


Page 26

Misalkan [

]

, maka harus ditunjukkan bahwa

. Andaikan

, maka

menurut algoritma pembagian, ada bilangan-bilangan bulat q dan r sedemikian sehingga :

Karena c adalah KPK dari a dan b, maka dan

dan

. Karena [

]

maka

.

maka

dan karena

, maka

. Ini berarti

maka

dan karena

, maka

. Ini berarti

Karena

dan

maka r adalah kelipatan persekutuan dari a dan b.

Tetapi karena [

]

dan

, maka hal tersebut tidak mungkin

(kontradiksi). Jadi pengandaian di atas tidak benar, berarti

atau [

]

Perhatikan bahwa [6,9]=18 dan [2.6, 2.9]=[12, 18] = 36. Tampak bahwa [2.6,2.9]=2[6,9]. Contoh : Tentukan KPK dari [

]

[

] [

[

]

[

] [

[

]

]

]

Teorema 2.13 Jika a dan b bilangan-bilangan bulat yang keduanya positif, maka : [

]

Contoh 1: [


]

Page 27

[

]

[ [

[

] ]

]

Contoh 2 : dan [


]

Page 28

BILANGAN PRIMA A. PENGERTIAN BILANGAN PRIMA Definisi : Bilangan prima adalah bilangan bulat positif yang lebih besar dari 1 dan tidak mempunyai faktor bilangan bulat positif kecuali 1 dan bilangan bulat itu sendiri. Contoh : Barisan bilangan prima : 2, 3, 5, 7, 11, 13, 17, 19, …

Definisi : Bilangan bulat positif yang lebih besar dari 1 dan bukan bilangan prima disebut bilangan komposit (tersusun). Contoh : Barisan bilangan komposit : 4, 6, 8, 9, 10, 12, 14, 15, …

Perhatikan bahwa 1 bukan merupakan bilangan prima ataupun bilangan komposit. Satu (1) disebut unit. Jadi himpunan semua bilangan bulat positif (bilangan asli) terbagi dalam tiga himpunan bagian yang saling lepas, yaitu himpunan semua bilangan prima, himpunan semua bilangan komposit, dan himpunan unit.

Lemma 1.1: Setiap bilangan bulat positif yang lebih besar dari 1 dapat dibagi oleh suatu bilangan prima. Bukti : Lemma dibuktikan dengan kontradiksi, diasumsikan bahwa ada bilangan bulat positif yang lebih besar dari 1 tetapi tidak punya pembagi berupa bilangan prima. Maka himpunan dari bilangan-bilangan bulat yang lebih besar dari 1 dengan pembagi bukan bilangan prima tidak kosong. Berdasarkan sifat wellordering himpunan tersebut mempunyai elemen terkecil sebut n. Bilangan n Pendidikan Matematika FKIP UMB-Yogyakarta

Page 29

bukan prima, sebab n n dan n tidak mempunyai pembagi prima. Maka dapat ditulis n = a.b dengan 1  a  n dan 1  b  n. Karena a  n, dan n terkecil yang tidak mempunyai pembagi prima, maka a mempunyai pembagi prima sebut p. Sehingga a = k.p dengan k bilangan bulat positif. Berdasarkan teorema 1.7, semua pembagi dari a adalah pembagi dari n. Dapat ditulis n = k.p.b jadi n mempunyai pembagi prima.

Teorema 1.17: (Teorema Euclides) Banyaknya bilangan prima adalah tak berhingga. Bukti : Mempertimbangkan bilangan bulat Qn = n! + 1, n ≥ 1 Menurut Lemma 1.1, menjelaskan bahwa Qn mempunyai paling tidak 1 pembagi prima, sebut qn. Maka qn pasti lebih besar dari pada n. Jika qn  n maka berlaku qn n! dan menurut teorema 1.8, maka qn  (Qn – n!) = 1. Hal ini tidak mungkin karena qn adalah suatu bilangan prima. Maka diperoleh bahwa tidak ada bilangan prima terbesar, dengan kata lain bahwa banyaknya bilangan prima adalah tak berhingga.

Pada

pembuktian

Teorema

Euclides

tersebut

yang

menarik

adalah

pembentukan bilangan bulat positif Qn sebagai hasil kali semua bilangan prima ditambah 1. Contoh : Q1 = 2 + 1 = 3 Q2 = 2.3 + 1 = 7 Q3 = 2.3.5 + 1 = 31 Q4 = 2.3.5.7 + 1 = 211 Q5 = 2.3.5.7.11 + 1 = 2311

dst Pendidikan Matematika FKIP UMB-Yogyakarta

Page 30

Teorema 1.18: Jika n suatu bilangan komposit, maka n memiliki faktor bilangan prima yang tidak lebih dari √ . Bukti : Jika n adalah bilangan bulat komposit, maka k √ untuk k merupakan faktor prima dari n. Karena n bulat komposit maka n = a.b, dimana a dan b Z dengan 1  a  b  n. Andaikan a = b, maka persamaan a.b = n  a2 = n  a = √ . Sehingga kita harus memiliki a  √ . Untuk membuktikannya kita menggunakan bukti tidak lengsung yaitu dengan menggunakan ingkaran dari a  √ yaitu a  √ dimana b  a  √ , sehingga a  √ dan b  √ , maka diperoleh a.b  √ √

= n  a.b  n.

Kontradiksi dengan n = a.b sehingga terbukti benar untuk a  √ . Berdasarkan Lemma 1.1, setiap bilangan bulat positif lebih dari 1 maka memiliki sebuah pembagi prima. Karena a  1, maka a seharusnya memiliki sebuah faktor prima misalkan k, sehingga k a. Menurut teorema 1.7, Jika k a dan k n, sehingga k merupakan faktor prima dari n. Karena k a maka k  a. Dari k  a dan a  √ dapat diperoleh k  √ . Teorema 1.20: untuk setiap bilangan bulat positif n, n merupakan bilangan bulat komposit positif Z = 1, 2, 3, 4, 5, 6, 7,8, 9, 10....... Komposit = 4, 6, 8, 9, 10,...... Bukti : dengan mempertimbangkan n urutan bilangan bulat positif Dimana : 2≤ j ≤ n + 1, kita ketahui bhwa j│(n + 1)!. Dari tteorema 1.8 menuruti j│(n + 1 )! + j sebab itu n merupakan urutan semua bilangan bulat composit: Contoh : 1.41 Tujuh merupakan urutan bilanagan bulat dengan di mulai dari 8! + 2 = 40322 adalah composite ( bagaimanapun ( Namun, ini merupakan tujuh bilangan composite terkecil, 90, 91,92,93,94,95, dan 96) Teorema 1.20 menujuk jarak antara urutan bilangan prima yang memiliki penyelesaian yang panjang. Disisi lain, bilanagan prima boleh, memungkinkan Pendidikan Matematika FKIP UMB-Yogyakarta

Page 31

bilngan prima yang saling berdekatan, urutan bilangan prima adalah 2 dan 3, karena 2 merupakan satu-satunya bilngan prima yang positive. Bagaimanapun banyak bilanagan prima yang selisih 2, ini merupakan pasangan bilangan prima yang disebut bilanagn prima kembar. Contoh adalah bilangan prima 5 dan 7, 11 dan 13, 101 dan 103, dan 4967 dan 4969. Kta tau bilangan prima terbesar adalah 1706595.211235 ± 1 sebuah dugaan yang belum terselesaikan yang menegaskan bahwa ada banyak bilangan prima kembar yang tak terhingga. ada banyak dugaan tentang jumlah bilangan prima dari berbagai bentuk. misalnya, tidak diketahui apakah ada bilangan prima tak terhingga bentuk n2 +1 dimana n adalah bilangan bulat positif. dugaan Goldbach's. Bahkan setiap bilangan bulat positif yang lebih besar, maka dua dapat ditulis sebagai jumlah dari dua bilangan prima. Contoh 1.42. Bilangan bulat 10, 24, dan 100 dapat ditulis dalam jumlah 2 bilangan prima dengan cara dibawah ini. 10 = 3+7 = 5+5 24 = 5+19 = 7+17 = 11+13 100 = 3+97 = 11+89 = 17+8 = 29+71 = 41+59 = 47+53 B.

Teori Dasar Aritmatika

Teori dasar aritmatik sangat penting untuk menunjukkan bilangan prima yang dibangun dari bilangan bulat. Disini teorinya berbunyi Teorema 2.7 Teori dasar aritmatika. Setiap bilangan bulat positif yang lebih besar dari satu dapat dituliskan sebagai hasil bilangan prima dengan faktor prima dalam bentuk yang tidak turun. Contoh 2.10: Faktorisasi dari bilangan positif dapat diberikan dengan 240 = 2.2.2.2.3.5 = 24.3.5 289 = 17.17 = 172 1010 = 7.11.13 Pendidikan Matematika FKIP UMB-Yogyakarta

Page 32

Penulisan di atas merupakan kombinasi semua bagian faktor utama yang masuk dalam prima. Masing-masing dapat dilihat di contoh. Dimana 240 seluruh faktornya berupa 2 dan dikombinasian berupa 24. Faktorisasi bilangan bulat yang merupakan faktor utama yang dapat dikombinasikan disebut sebagai faktor pokok utama (prime- power factorizations). Untuk membuktikan teori dasar aritmatika, kita membutuhkan lemma dibawah ini. Lemma 2.3 Jika a, b dan c bilangan bulat positif maka

dan

.

sehingga

Bukti: Dimana

untuk sembarang bilangan bulat x dan y seperti ax + by = 1.

Perkalian keduanya merupakan persamaan dengan c, dimana acx + bcy = c, berdasarkan theorem 1.8, a membagi acx + bcy, yang merupakan kombinasi linear untuk ac dan bc, yang mana keduanya dapat dibagi dengan a sehingga

.

Lemma.2.4 Jika

p

membagi

dimana

p

adalah

prima

dan

adalah bilangan bulat positif, maka terdapat bilangan bulat I dengan 1 ≤ i ≤ n sedemikian hingga p membagi ai Bukti; Kita membuktikannya dengan induksi. Kasus ini, dimana n = 1 barupa trivial. Diasumsikan bahwa hasilnya benar untuk setiap n. pertimbangkan bahwa a merupakan hasil dari n + 1 berupa bilangan bulat a1, a2, a3 . . . . an+1 dapat dibagi dengan bilangan prima p. sehinga perhatikan jika

atau

Sekarang

. dari hipotesis induksi dimana setiap

bilangan bulat i dengan 1 ≤ i ≤ n sehingga

. Konsekuensinya

untuk

semua i dengan 1 ≤ i ≤ n +1. Untuk memulai membuktikan teorima dasar aritmatika, pertama kita mulai menunjukkan bahwa setiap bilangan bulat positive lebih besar dari 1 dapat ditulis menjadi sebagai hasil prima, setidaknya dengan satu cara. Kemudian kita menunjukkan hasil yang unik (berlainan) untuk beberapa prima yang ada.


Page 33

Bukti: Kita membuktikan dengan kontradiksi. Diasumsikan bahwa samua bilangan bulat positif tidak dapat ditulisakan sebagai hasil prima. Terdapat n paling kecil dari bilangan bulat (well-ordering property). Jika n adalah prima, ini merupakan sebenar-benar hasil untuk himpunan prima, dimanakan prima pertama n. sehingga n adalah komposit. Nampak bahwa dan

dengan

. Tetepi a dan b lebih kecil dari pada n maka harus

dijadikan sebagai hasil prima. Kemudian jika

kita simpulkan bahwa n

juga hasil dari prima. Ini terjadi kontradiksi yang ditunjukkan bahwa setiap bilangan bulat positif dapat dibentuk sebagai hasil dari prima. Kita bisa menunjukkan bahwa teori dasar aritmatika dapat ditunjukkan bahwa faktor-faktornya merupakan bilangan yang berbeda (unik)

Dimana

adalah semua prima dengan

dan

.

Sehingga semua prima yany sama dari dua faktor didapatkan

dimana prima sebelah kiri untuk persamaan yang berbeda dari hasil sebelah kanan. u ≥1 dan v ≥ 1 (dua faktor yang asli dikira itu berbeda), Bagaimanapun, terjadi kontradiksi dengan lemma2.4 bahwa lemma tersebut

pi

harus

membagi qi untuk semua i. Hal tersebut tidak mungkin, dimana masing-masing qi berupa prima dan berbeda dengan pi karenanya faktor prima u/ bilangan bulat positif n adalah berbeda. Faktor prima bilangan bulat selalu dapat digunakan, sebagaimana contoh Contoh 2.13. Kelipatan berikut yang paling umum [15,21] = 105, [24,36] = 72, [2,20] = 20,dan [7,11] = 77. Setelah faktorisasi utama a dan b diketahui, mudah untuk menemukan [a, b]. Jika

a  p1a1 p2a2 ....pnan danb p1b1 p2b2 ....pnbn dimana p1, p2,...,pn adalah bilangan


Page 34

prima terjadi di faktorisasi prima yang terbesar a dan b, maka untuk bilangan bulat dapat dibagi oleh a dan b, perlu diketahui bahwa dalam faktorisasi bilangan bulat, masing-masing sama besar dengan

pj terjadi

aj dan bj Oleh

dengan yang terbesar di kurangnya

karena itu, [a, b], bilangan bulat positif

terkecil yang habis dibagi oleh a dan b adalah [a,b] = p1max(a1,b1) p2max(a2,b2)...... pnmax(an,bn) Dimana max (x,y) menandakan, besar atau maksimal dari x dan y menemukan faktorisasi utama largers memakan waktu. Oleh karena itu, kami akan memilih sebuah metode untuk menemukan beberapa yang paling umum dari dua bilangan bulat tanpa menggunakan factorizations utama bilangan bulat tersebut. Kami akan menunjukkan bahwa kita dapat menemukan beberapa yang paling umum dari dua bilangan bulat positif setelah kita mengetahui pembagi umum terbesar dari bilangan bulat. Yang terakhir ini dapat ditemukan melalui algoritma Euclidean. Pertama, kita membuktikan lemma berikut lemma 2.5 Jika x dan y adalah angka riil, maka max (x, y) + min (x, y) = x + y Bukti: -

Jika



maka

dan

, sehingga

, -

Jika

, kemudian

dan

, dan kita juga = x+y

akan menemukan bahwa

kita gunakan teorema berikut ini untuk menemukan [a,b] x (a,b) di ketahui Teorema 2.8 Jika a dan b adalah bilangan bulat positif, maka [

]

, dimana [a, b]

dan (a,b) adalah KPK dan FPB dari a dan b berurutan. Bukti. diberikan a dan b mempunyai faktorisasi prima berpangkat dan

b p1b1 p2b2 ....pnbn ,


a  p1a1 p2a2 ....pnan

dimana eksponennya berupa bilangan bulat tak negatif

Page 35

dan semua bilangan prima merupakan faktor pada keduanya, mungkin dengan eksponen nol. Sekarang diberikan

Mj max( aj,bj )

dan

mj min( aj,bj ).

kemudian kita dapatkan [a,b] (a,b)

= p1M1 p2M2 .....pnMn p1m1 p2m2 ....pnmn =

p1M1m1 p2M2m2 ....pnMnmn

=

p1a1b1 p2a2b2 ....pnanbn

=

p1a1 p2a2 ...pnan p1b1 ...pnbn

=

ab

aj ,bj ) min( aj,bj ) aj bj berdasaran lemma 2.5 Karena Mj mj max( Konsekuensi berikut ini untuk teorema dasar aritmatika yang akan digunakan nanti CONTOH : Misalkan a = 6 dan b =8 [6,8]=24 dan (6,8)=2 [ [

] ]

Lemma 2.6. Ambil m dan n bilangan bulat positif yang relatif prima. Kemudian jika d adalah pembagi positif dari mn, dimana ada sepasang bilangan positif pembagi

d1

untuk m dan

d2 dari n sedemikian sehingga d = d1 d2 . Jika d1 dan d2 adalah pembagi positif dari m dan n secara berurutan, maka d = d1 d2 adalah pembagi positif dari mn, Bukti, Diberikan faktorisasi prima berpangat untuk m dan n, dimana m =

p1m1 p2m2 .....psms dan n q1n1q2n2 .....qtnt karena (m, n) =1, himpunan bilangan prima p1, p2,......ps dan himpunan bilangan prima q1,q2,...... qt tidak memiliki elemen sama/peskutuan. Oleh karena itu, faktorisasi prima berpangat mn adalah

mn p1m1 p2m2 ....psms q1n1q2n2 .....qtnt Pendidikan Matematika FKIP UMB-Yogyakarta

Page 36

Karena, jika d pembagi positif dari mn, maka

d  p1e1 p2e2 ....pses q1f1q2f2 .....qtft Dimana 0e1 mi untuk i = 1,2,…..,s dan 0 f j nj untuk j = 1,2,…,t. Dimana bahwa

d1 (d,m)dan d2 (d,n) sehingga

d1  p1e1 p2e2 ....pses dan

d2 q1f1q2f2 ....qtft Jelas

d d1d2 dan (d1,d2) 1.

Ini adalah dekomposisi d yang kita inginkan.

Selanjutnya dekomposisi adalah unik (tunggal). Untuk melihat ini, Perhatikan bahwa setiap pangkat prima dalam faktorisasi d harus ada

d1

atau

d2 ,

dan

pangkat prima dalam faktorisasi d yang pangkat primanya membagi m harus muncul dalam d1 , sedangkan pangkat prima dalam faktorisasi d pangkat prima yang membagi n harus muncul dalam menunjukkan bahwa d1 harus menjadi (d, m) dan Conservely, diberikan

d1 dan d2

tersebut

d2 harus menjadi (d, n)

positif yang membagi dari m dan n, secara

d1  p1e1 p2e2 ....pses

berrutan. maka Dimana

d2 . Langkah

berupa

0e1 mi untuk i = 1,2,…..,s dan d2 q1f1q2f2 ....qtft

Dimana

0 f j nj untuk j = 1,2,…,t. bilangan bulat

d d1d2  p1e1 p2e2 ....pses q1f1q2f2 .....qtft Jelas merupakan pembagi dari

mn p1m1 p2m2 ....psms q1n1q2n2 .....qtnt karena pangkat untuk prima ada di faktorisasi prima berpangkat untuk

d

kurang dari atau sama dengan pangkat prima yang terdapat pada faktorisasi prima berpangkat untuk mn. Hasil kesepakatan yang terkenal dengan teori bilangan bilangan prima di barisan aritmatika.l Teorema 2.9. teorema Dirichlet's bilangan prima di barisan aritmatika Pendidikan Matematika FKIP UMB-Yogyakarta

Page 37

a dan b bilangan bulat positif yang relatif prima. kemudian progresi aritmetik sebuah + b, n = 1,2,3 ,...., mengandung banyak bilangan prima tak terhingga. G. Lejeune Dirichlet, membuktikan teorema ini pada tahun 1837. Sejak bukti Teorema Dirichlet sangat rumit dan mengandalkan teknik-teknik canggih, kami tidak menunjukkan bukti di sini. Namun, tidak sulit untuk membuktikan kasuskasus khusus dari teorema Dirichlet's, sebagai gambaran teorema berikut. Teorema 2.10 Terdapat tak hingga banyak prima untuk 4n + 3 dimana n adalah bilangan bulat positif Lemma 2.7 Jika a dan b adalah bilangan bulat yang keduanya berbentuk 4n + 1, maka hasil ab juga dari bentuk tersebut. Bukti Diketahui a dan b berbentuk 4n + 1, disini terdapat bilangan bulat r dan s sedemikian hingga a = 4r + 1 dan b = 4s + 1. Karena ab = (4r + 1)(4s + 1) = 16rs + 4r + 4s + 1 = 4 (4rs + r + s) + 1 = 4 n + 1 dimana n = 4rs + r + s Bukti Theorema 2.10 Diasumsikan bahwa hanya ada satu angka prima dari bentuk 4n + 3, katakan po= 3, p1, p2, . . . pr jika diberikan Q = 4p1, p2, . . . pr + 3 maka terdapat paling sedikit satu prima dalam faktorisasi Q untuk bentuk 4n + 3. Bukti lain Semua prima dapat dibentuk 4n + 1 dan dengan lemma 2.7 hal ini dapat diimplikasikan bahwa Q juga dapat dibentuk seperti itu. Terjadilah kontradiksi. Bagaimanapun tidak ada bentuk prima po, p1, p2, . . . pr membagi Q. Bilangan prima 3 tidak membagi Q. Pendidikan Matematika FKIP UMB-Yogyakarta

Page 38

Jika 3| Q, maka 3| (Q – 3) = 4 p1, p2, . . . pr. Jelas terdapat kontradiksi Cara Yang Paling Enak Tidak ada satu bilangan prima pj yang membagi Q. kerana pj tidak membagi Q berimplikasi pj tidak membagi (Q – 4p1, p2, . . . p3) = 3. Karenanya, terdapat bilangan prima dari bentuk 4n + 3 yang tidak terhingga. Pada bagian ini , kita dapat menyimpulkan beberapa hasil pembuktian tentang bilangan irrasional. Jika α adalah bilangan rasional maka kita boleh menulis α sebagai hasil bagi dua bilangan bulat tak terhingga, jika α = a/b dimana a dan b adalah bilangan bulat dengan b ≠ 0 maka α = ka/kb, k ≠ 0. Hal ini mudah untuk mengetahui

bahwa suatu bilangan rasional positif dapat ditulis sebagai

pembagian dua bilangan bulat relative prima. Ketika kita mengetahui bahwa bilangan rasional adalah bentuk yang paling rendah (lowest Terms). Kita menuliskan bahwa bilangan 11/21 sebagai bentuk terendah. Kita juga melihat bahwa . . . . ,– 33/- 36, - 11/-21 , . . .

dari dua hasil ini ditunjukkan bahwa

terdapat bilangan rasionala tertentu. Kita mulai dengan memberikan bukti lain yaitu bilangan irrasional

2

Bukti: Misalkan

2 rasional. Maka 2 = a/b. dimana a dan b bilangan bulat relative

prima, b≠0. Jika 2 = a2/b2 maka 2b2 = a2. Karenanya 2|a2 (berdasarkan teorema dasar aritmatika) maka 2|a. diberikan a = 2c, maka b2=2c2 maka 2|b2 dan juga 2|b. bagaimanapun (a,b)=1 kita mengetahui bahwa 2 tidak dapat membagi a dan b. ini kontradiksi sehingga

2 adalah irrasional. Kita dapat juga mengeneralisaikan hasil 2 sebagai irrasional. Teorema 2.11 Diberikan α sebagai akar polynomial xn + cn-1xn-1 + …. + c1x + c0 dimana koefesien co, c1, ….. , cn-1 adalah bilangan bulat, maka α juga merupakan bilangan bulat atau bilangan irrasional Bukti Dengan kontradiksi


Page 39

Diasumsikan bahwa α adalah rasional. Kita menuliskan α = a/b dimana a dan b adalah bilangan bulat relative prima dengan b ≠ 0. Jika α adalah akar dari xn + cn-1xn-1 + …. + c1x + c0 Maka didapat (a/b)n + cn-1(a/b)n-1 + …. + c1(a/b) + c0 = 0 Perkalian dengan bn didapatkan an + cn-1an-1b + …. + c1abn-1 + c0 bn = 0 an = b (- cn-1an-1 - …. - c1abn-2 + c0 bn-1) kita lihat bahwa b|an. Diasumsikan bahwa b ≠ ±1, maka b mempunyai pembagi prima p. Jika p|b dan b|an, kita tahu bahwa p|an, sehingga p|a. bagaimanapun (a,b) = 1. Ini jelas kontradiksi dengan yang ditunjukkan bahwa b = ± 1. Konsekuensinya, jika α adalah irrasional maka α = ± a sehingga α pasti berupa bilangan bulat. Contoh Diberikan a bilangan bulat positif yang tidak memiliki pengkat m bilangan positif, maka x = m a tidak bilangan bulat. Maka m a adalah bilangan irrasional. Karenanya m a akar dari xm – a . akibatnya semua angka

2,3 5,1017 adalah

irrasional.


Page 40

PENGANTAR KEKONGRUENAN A. PENDAHULUAN

Bahasa khusus kongruen yang kami perkenalkan dalam bab ini sangat berguna dalam teori bilangan. Bahasa kekongruenan ini dikembangkan pada awal abad ke-19 oleh Karl Friedrich Gauss, salah satu matematikawan paling terkenal dalam sejarah. Definisi . Jika a, b

Misalkan

, kita peroleh bahwa a kongruen dengan b

modulo m jika m | (a – b). Jika a kongruen b modulo m, kita tuliskan b), kita tuliskan

(mod m). Jika m (a –

(mod m), dan dikatakan bahwa a dan b tidak

kongruen modulo m. Contoh 3.1 

(mod 9) karena 9 | (22 – 4) = 18 gunakan teorema 3.1 (22= 4+2.9) bisa ditulis 22 kongruen dengan 4 modulo 9



(mod 9) dan



(mod 9) karena 9 (13-5) = 8

(mod 9)

Kekongruenan sering muncul dalam kehidupan kita sehari-hari. Misalnya, pada jam bekerja baik modulo 12 maupun modulo 24 untuk jam, dan modulo 60 untuk menit dan detik, kalender bekerja pada modulo 7 untuk hari dalam seminggu dan modulo 12 untuk bulan. Meteran serba guna sering beroperasi pada modulo 1000 dan odometer bekerja pada modulo 100000.


Page 41

Ketika bekerja menggunakan kekongruenan, akan sangat berguna mengubah ke kesamaannya. Untuk melakukan hal ini, diperlukan teorema di bawah ini. Teorema 3.1 Jika a dan b bilangan bulat, maka

(mod m) jika dan hanya jika ada

suatu bilangan bulat k sedemikian sehingga a = b + km. Bukti: (mod m), maka

Jika

–

. Ini berarti bahwa ada suatu k bilangan

– , sehingga a = b + km.

bulat dengan (22= 4+2.9)

Sebaliknya, jika ada bilangan bulat k dengan a = b + km, kemudian km = a – b. Oleh karena itu,

–

dan akibatnya,

(mod m).

Contoh 3.2 

19 ≡ -2 (mod 7) dan 19 = -2 + 3.7

Proposisi berikut menetapkan beberapa sifat penting dalam kekongruenan. Teorema 3.2 Misal m suatu bilangan bulat. Kekongruenan modulo m memenuhi sifat-sifat berikut: (i) Refleksif. Jika a suatu bilangan bulat, maka (ii) Simetris. Jika a dan b

sedemikian sehingga

(mod m), maka

(mod m) (iii) Transitif. Jika a, b, dan c maka

dengan

(mod m) dan

(mod m),

(mod m).

Bukti: (i) Kita lihat bahwa Pendidikan Matematika FKIP UMB-Yogyakarta

(mod m) karena m| (a – a) = 0

Page 42

(mod m) maka m | (a – b). Oleh karena itu, ada suatu bilangan k

(ii) Jika dengan

sehingga m | (b –

. Hal ini menunjukkan

a). akibatnya,

(mod m)

(mod m), dan

(iii) Jika

(mod m), maka m | (a – b) dan m | (b – c).

Oleh karena itu, ada bilangan bulat k dan l

dengan

. Oleh karena itu,

dan .

Ini menunjukkan bahwa m | (a – c) dan

(mod m).

Berdasarkan Teorema 3.2, dapat kita peroleh bahwa himpunan bilangan bulat dapat dibagi ke dalam m himpunan berbeda yang disebut kelas kekongruenan modulo m, masing-masing kelas terdiri atas bilangan bulat yang saling kongruen modulo m. Contoh 3.3 Kesesuaian 4 kelas kekongruenan modulo 4 sebagai berikut: (mod 4) (mod 4) (mod 4) (mod 4) Misalkan m adalah bilangan bulat positif. Diberikan suatu bilangan bulat a, dengan algoritma pembagian kita dapatkan a = bm + r dimana 0 ≤ r ≤ m – 1. Kita sebut r sebagai residu terkecil nonnegatif dari a modulo m. Kita katakan bahwa r adalah hasil dari pengurangan a modulo m. Kita juga menggunakan notasi a mod m = r untuk menunjukkan bahwa r adalah residu yang diperoleh ketika a dibagi m. Contoh: 17 mod 5 = 2 dan -8 mod 7 = 6. Dari persamaan a = bm + r, ini berarti

(mod m). Oleh karena

itu, setiap bilangan bulat kongruen modulo m dengan tepat satu bilangan bulat pada himpunan 0, 1, ...,

m – 1. Karena tidak ada dua bilangan bulat

0, 1, ..., m – 1 yang kongruen modulo m, maka kita memiliki m bilangan


Page 43

bulat sedemikian sehingga setiap bilangan bulat kongruen tepat satu dari m bilangan bulat itu. Definisi Sistem residu lengkap modulo m adalah himpunan bilangan bulat sedemikian sehingga setiap bilangan bulat kongruen modulo m dengan tepat satu bilangan bulat pada himpunan tersebut. Contoh 3.4 Algoritma Pembagian menunjukkan bahwa himpunan bilangan bulat 0, 1, 2, . . .,

m – 1 adalah sistem residu lengkap modulo m. System tersebut

disebut himpunan residu terkecil nonnegative modulo m. Contoh 3.5 Misal m adalah suatu bilangan bulat ganjil, maka himpunan bilangan bulat , . . ., -1, 0, 1, . . .,

,

himpunan residu terkecil mutlak modulo m, adalah system lengkap residu.

Kita akan sering melakukan perhitungan dengan kekongruenan. Kekongruenan memiliki banyak sifat yang sama dengan suatu persamaan. Teorema 3.3 Jika a, b, c dan m adalah bilangan bulat dan

sedemikian sehingga

, maka (i)

(mod m),

(ii)

(mod m), (mod m)

(iii) Bukti:

, maka m | (a – b).

Karena (i)

bisa kita uraikan menjadi ekuivalen dengan m |


sehingga m | (a – b) sehingga (i) terpenuhi

Page 44

(ii)

sehingga m | (a – b)

bisa kita uraikan menjadi ekivalen dengan m |

sehingga (ii) terpenuhi

(iii) Untuk menunjukkan (iii) terpenuhi, kita tahu bahwa Karena

–

–

, maka ini dipenuhi juga untuk

–

. Oleh

(mod m)

karena itu, Contoh 3.3 1. 2. Contoh : 3. Contoh :

Contoh 3.6 maka berdasar teorema 3.3

Karena 

(mod 8),



(mod 8),



(mod 8)

Apa yang terjadi bila kedua ruas kekongruenan dibagi dengan suatu bilangan bulat? Perhatikan contoh di bawah ini. Contoh 3.7 Kita memiliki

(mod 6). Tetapi kita tidak dapat

menghilangkan faktor persekutuan dari 2 sehingga

(mod 6).

Contoh di atas menunjukkan bahwa sifat kanselasi tidak berlaku sepenuhnya pada relasi kekongruenan. Sifat kanselasi akan berlaku dengan suatu syarat seperti dinyatakan dalam teorema berikut ini. Teorema 3.4 Jika a, b, c dan m adalah bilangan bulat sedemikian sehingga m) dan

(mod m) maka

, d = gcd(c,

)

Bukti:


Page 45

(mod m), kita ketahui bahwa

Jika

–

Oleh

–

karena itu, ada suatu bilangan bulat k di mana c(a – b) = km. Dengan membagi kedua ruas dengan d, kita peroleh (

)

Karena

–

, berdasarkan lemma 2.3 maka terpenuhi juga

.

Dengan demikian

Contoh 3.8 Karena

dan atau

, kita lihat bahwa

(mod 3)

Corollary berikut ini, yang merupakan masalah khusus teorema 3.4, sering digunakan. Corollary Jika a, b, c, dan m suatu bilangan bulat sedemikian hingga (mod m) maka

dan

, (c, m) = 1

(mod m).

Contoh 3.9 Karena

(mod 5) dan (5,7) = 1, kita simpulkan bahwa

(mod 5) atau

⁄

⁄

(mod 5).

Teorema 3.5 Jika a, b, c, d, dan m bilangan bulat sedemikian hingga hingga (mod m) dan

,

(mod m) maka:

(i)

(mod m)

(ii)

(mod m) (mod m)

(iii) Bukti:

(mod m) dan

Karena

(mod m), kita tahu bahwa m | (a – b) dan m

| (c – d). Oleh karena itu, ada bilangan bulat k dan l dengan

dan

. (i) Pendidikan Matematika FKIP UMB-Yogyakarta

.

Page 46

Oleh karena itu,

(mod m)

] sehingga

[

(ii)

. Oleh karena itu,

(mod m)

] sehingga

[

(iii) . Oleh karena itu,

(mod m)

sehingga

Contoh 3.10 Karena

(mod 5) dan

(mod 5), menggunakan teorema 3.5 kita

peroleh bahwa: dan 

(mod 5)



(mod 5)



(mod 5)

Teorema 3.6 adalah sistem residu lengkap modulo m, maka jika a

Jika

adalah bilangan bulat positif dengan

, maka

adalah sistem residu lengkap modulo m untuk sebarang bilangan bulat b. Bukti: Pertama, kita tunjukkan bahwa tidak ada dua bilangan bulat yang kongruen modulo m. Untuk menunjukkannya, perhatikan bahwa jika (mod m) maka berdasar (ii) teorema 3.3, kita peroleh (mod m) Karena

, Corollary 3.4 menyatakan bahwa (mod m)


Page 47

Karena

(mod m) jika

, kita simpulkan bahwa

Theorema 3.7 Jika

dan

adalah bilangan bulat dengan

maka

dan

.

Bukti : Karena

…..(1)

dengan demikian

…..(2)

Karena

dan

maka

(theorema 1.7)

Sehingga Contoh 3.11 Karena

, maka dengan theorema 3.7 didapatkan bahwa

Theorema 3.8 Jika

, adalah bilangan bulat dengan [

bulat positif maka dari

dengan bilangan

] ;[

] adalah KPK

.

Bukti: Karena

maka

[

] [

Akibatnya

]

Contoh : ,

dan [


]

Page 48

Corollary 3.8.1 Jika

, dengan

bilangan bulat dan

adalah

adalah bilangan bulat positif relative prima

yang berpasangan, maka

.

Bukti: Karena [

adalah bilangan relative prima yang berpasangan maka ]

. Dengan teorema 3.8, kita peroleh .

Dalam studi berikutnya, kita akan bekerja dengan kekongruenan dengan pangkat besar bilangan bulat. Sebagai contoh, kita ingin menemukan residu positif terkecil dari 2644 modulo 645. Jika kita mencoba untuk menemukan residu positif terkecil dengan menghitung 2644, kita akan memiliki suatu bilangan dengan 194 desimal digit. Sebaliknya, untuk menemukan 2644 modolo 645 pertama-tama kita tuliskan eksponen 644 dalam notasi biner: (644)10=(1010000100)2 Selanjutnya, kita menghitung residu positif terkecil dari 2, 22 ,24 ,28 ....2512 dengan berturut mengkuadratkan dan mengurangi modulo 645, sehingga diperoleh (mod 645) (mod 645) (mod 645) (mod 645) (mod 645) (mod 645) (mod 645) (mod 645) (mod 645) (mod 645) Sekarang kita akan menghitung modulo 645 dengan mengalikan residu positif terkecil dari pangkat 2, diperoleh Pendidikan Matematika FKIP UMB-Yogyakarta

Page 49

(mod 645) Kita baru saja mengilustrasikan prosedur umum untuk perpangkatan modulo, untuk menghitung modulo m, di mana b, m dan N adalah bilangan bulat positif. Pertama kita menuliskan pangkat N dalam notasi binari, sebagai N = . Kemudian mencari residu positif terkecil dari modulo m, dengan berturut-turut mengkuadratkan dan mengurangi modulo m. Terakhir, kalikan residu positif terkecil modulo m dari untuk j dengan a =1, kurangkan dengan modulo m setelah perkalian. Theorema 3.9 Misalkan b, m, dan N adalah bilangan bulat positif dengan b < m, maka residu positif terkecil dari modulo m dapat dihitung dengan menggunakan 2 operasi bit O((log2m) log2N) Bukti: 3.1. Kekongruenan Linear Kekongruenan dengan bentuk (mod m) di mana x adalah sebarang bilangan bulat, disebut kekongruenan linear dalam satu variabel. Di sesi ini, kita akan melihat bahwa ilmu yang mempelajari kekongruenan sama dengan ilmu yang mempelajari mengenai persamaan diophantin linear dalam dua variabel. Perhatikan bahwa jika merupakan solusi dari kekongruenan (mod m)., dan jika (mod m), maka (mod m), sehingga juga merupakan solusi. Sehingga, jika salah satu anggota kekongruenan modulo kelas m merupakan solusi, maka semua anggota kelas ini merupakan solusi. Oleh karena itu, kita dapat bertanya, berapa banyak m kekongruenan kelas modulo m memberi solusi, ini sama dengan bertanya berapa banyak solusi yang tak kongruen pada modulo m. Teorema berikut menyebutkan kapan suatu kekongruenan linear dalam satu variabel memiliki solusi, dan jika memiliki solusi, menyatakan berapa banyak solusi tak kongruen yang ada pada modulo m dengan tepat. Teorema 3.10 Misal a, b dan m adalah bilangan bulat di mana dan (a, m) = d. Jika maka (mod m) tidak memiliki solusi. Jika d | b, maka (mod m) memiliki tepat d solusi tak kongruen modulo m. Bukti: Dengan menggunakan Teorema 3.1, kekongruenan linear ekivalen dengan persamaan diophantin linear dalam dua variabel. Bilangan bulat x adalah solusi dari (mod m) Pendidikan Matematika FKIP UMB-Yogyakarta

(mod m) .

Page 50

Contoh : Tentukan nilai x sehingga berlaku kekongruenan linier

Jawab Langkah 1. Mencari Langkah 2. Membuktikan . Terbukti Langkah 3. Memasukkan nilai d ke persamaan linier kekongruenan

Contoh : Carilah nilai x agar menjadi solusinya

Sehingga merupakan solusi 3.3 Teorema Sisa China Pada sesi ini dan satu sesi selanjutnya, kita akan mendiskusikan system kekongruenan yang simultan. Kita akan mempelajari 2 tipe such system. Pada tipe pertama, ada dua atau lebih kekongruenan linear dalam satu variabel, dengan modulo yang berbeda. Tipe kedua terdiri dari lebih dari 1 kekongruenan yang simultan pada lebih dari satu variabel, di mana semua kekongruenan memiliki modulus yang sama. Pertama, kita consider(menentukan??) system kekongruenan yang involve (hanya terdiri atas???) satu variabel, tetapi dengan modulo yang berbeda Teorema 3.3 Jika a, b, c dan m adalah bilangan bulat dengan m 0 sedemikian sehingga (mod m), maka (i) (mod m) (ii) (mod m) (iii) (mod m) Bukti Dari (mod m), kita ketahui bahwa m | (a – b). (i) Dari hukum identitas, Pendidikan Matematika FKIP UMB-Yogyakarta

Page 51

Jadi bisa kita buat m | (a – b) sama dengan m | Sehingga (i) terpenuhi (ii) Terpenuhi dari fakta bahwa Sehingga m | (a – b) sama dengan (iii) Perhatikan bahwa . Karena m | (a – b), maka terpenuhi juga m | c(a – b).


Page 52

PERSAMAAN LINEAR DIOPHANTINE

Pengantar /. Dalam kehidupan setiap hari, kita sering terlibat dalam masalah-masalah yang melibatkan perhitungan. Contohnya jika kita mempunyai uang sebesar Rp. 50.000, uang tersebut digunakan untuk membeli buku dan pensil. Harga Sebuah buku Rp.5000 dan pensil Rp.2500. Berapa banyak buku dan pensil yang dapat dibeli dari jumlah uang sebanyak 50.000 tadi? Untuk memecahkan masalah di atas, kita misalkan buku= x dan pensil=y, maka persamaan yang dapat dibentuk adalah 5000x +2500y = 50000. Tugas kita selanjutnya adalah mencari solusi dari masalah di atas, yaitu mencari nilai x dan y yang memenuhi persamaan tersebut. Dari contoh di atas koefisien nilai x dan y serta akar-akar persamaan merupakan anggota bilangan bulat, maka contoh di atas adalah salah satu contoh persamaan linear Diophantine (persamaan yang akar akarnya adalah bilangan bulat). Teorema 2.14 Untuk a dan b bilangan bulat dengan d = (a,b), Persamaan ax + by = c tidak mempunyai solusi bilangan bulat jika d ∣ c. Jika d∣c, maka terdapat tak berhingga banyak solusi dari bilangan bulat. Selain itu jika x= dan y= adalah bagian solusi dari persamaan maka semua solusi akan diberikan oleh: x= + (b/d)n, y= – (a/d)n, dimana n adalah bilangan bulat Bukti: Asumsikan bahwa x dan y anggota bilangan bulat sedemikian sehingga ax +by = c. Maka karena d∣a dan d∣b diperoleh d∣c, karena itu jika d ∣ c persamaan itu tidak mempunyai solusi. (d∣ax+bc=d∣c, dari teorema 1.8) Sekarang kita Asumsikan d∣c, dari teorema 2.2 (d=ma + nb) diperoleh d = as + bt

……………………. (2.3)

Karena d∣c berarti ada bilangan bulat e dengan c=de Kalikan (2.3) dengan e c = (as + bt)e Pendidikan Matematika FKIP UMB-Yogyakarta

Page 53

c = a (se) + b (te) salah satu solusi yang diberikan adalah x=

dan y=

, dimana

=se dan

=te.

Sekarang akan diperlihatkan bahwa ada tak berhingga banyaknya solusi dari persamaan, ambil x= +(b/d)n dan y=

– (a/d)n, dimana n adalah anggota bilangan bulat.

Kita peroleh pasangan (x,y) adalah solusi karena ax + by = a(

+ (b/d)n) + b(

=

+ a(b/d)n + b =

+b

– (a/d)n) – b(a/d)n

=c

Sekarang akan diperlihatkan setiap solusi dari persamaan

ax + by = c.

Andaikan x dan y adalah bilangan bulat dengan ax+ by = c. Karena

+b

oleh pengurangan diperoleh ax + by =

+b

ax + by - ( (ax –

+b

=0

) + (by- b

a(x – ) + b(ya(x – ) = b( kedua ruas dibagi dengan d, sehingga diperoleh (a/d)(x – ) = (b/d)( Dari teorema 2.1 (a/d,b/d)= 1, diperoleh (a/d)(x – ) , (b/d)(

= 1,

maka dengan menggunakan lemma 2.3 (jika a,b,c adalah bil. Bulat positif dimana (a,b)= 1 dan a∣bc maka a∣c). berarti (a/d)∣( Karena n adalah anggota bilangan bulat dengan

. (a/d)n = (

berarti y=

(a/d)n

masukan nilai y untuk mencari nilai x a(x – ) = b( a(x – ) = b(a/d)n x=

+ (b/d)n


Page 54

teorema ini digunakan untuk menentukan solusi dari persamaan linear (ax+by=c) dimana a,b,c mempunyai GCD Contoh Soal : 1. Tentukan semua bilangan bulat yang memenuhi persamaan:

21x + 14y = 70

Jawab Gunakan teorema Euclid untuk menentukan GCD dari 21 = 14 x 1 + 7 14 = 7 x 2 + 0 GCDnya adalah 7, dan karena 70 habis dibagi 7 (7∣70) maka persamaan ini mempunyai solusi. Ambil persamaan terakhir 7 = 21 – (1 x 14) 7 = (1 x 21) – (1 x 14) ………. Dikalikan 10 70 = (10 x 21) – (10 x 14) Jadi diperoleh solusi x=

10 dan

= -10.

+ (b/d)n

= 10 + (14/7)n = 10 + 2n y=

(a/d)n

= -10 – (21/7)n = -10 -3n Jika n = 1 -> x = 12 dan -13. Buktikan 21. 12 + 14. -13 = 70 Untuk semua n adalah anggota bilangan bulat. 2. Dalam kehidupan setiap hari, kita sering terlibat dalam masalah-masalah yang melibatkan perhitungan. Contohnya jika kita mempunyai uang sebesar Rp. 50.000, uang tersebut digunakan untuk membeli buku dan pensil. Harga Sebuah buku Rp.5000 dan pensil Rp.2500. Berapa banyak buku dan pensil yang dapat dibeli dari jumlah uang sebanyak 50.000 tadi? Jawab : Misalkan x = buku dan y = pensin 5000 x + 2500 y = 50.000 atau 50 x + 25 y = 500 Langkah 1. Mencari Pendidikan Matematika FKIP UMB-Yogyakarta

Page 55

dikalikan 10 Sehingga

x=

dan

+ (b/d)n

= 0 + (25/25)n =n y=

(a/d)n

= 20 – (50/25)n = 20-2n n = 1-> x =1 dan y = 18.

50.1 + 25.18=500 3. Tentukan semua bilangan bulat yang memenuhi persamaan: 15x+6y=189

Jawab: Pertama, kita tentukan GCD-nya dulu menggunakan algoritma Euclid. 15 = 6 x 2 +3 6 = 3 x 2 + 0. Jadi, GCD(15,6) = 3. Perhatikan bahwa 189 itu habis dibagi 3 (atau 3 189). Artinya, persamaan itu punya solusi x dan y. Lalu, ambil persamaan terakhir 3 = 15 - 6 x 2 3 = 1 x 15 - 2 x 6 …………….(dikali 63) 189 = 63 x 15 - 126 x 6 Dari sini, diperoleh satu solusi, yaitu

= 63 dan

= -126 (lihat bentuk

gcd(a,b)=ax+by)... x=

+ (b/d)n

= 63 + (6/3)n = 63 + 2n y=

(a/d)n


Page 56

= -126 – (15/3)n = -126 -5n


Page 57

KRIPTOLOGI 7.1 Karakter cipher Dari zaman kuno, pesan sekarang rahasia telah dikirim. Klasik, kebutuhan untuk komunikasi rahasia telah terjadi di dalam urusan diplomasi dan militer. Sekarang, dengan komunikasi elektronik yang masuk ke digunakan secara luas, kerahasiaan telah menjadi isu penting. Baru-baru ini, dengan munculnya perbankan elektronik, kerahasiaan telah menjadi diperlukan bahkan untuk transaksi keuangan. Oleh karena itu, ada banyak kepentingan dalam teknik pembuatan pesan dimengerti untuk semua orang kecuali penerima yang dimaksud. Sebelum membahas sistem kerahasiaan khusus, kami menyajikan beberapa terminologi. Disiplin yang ditujukan untuk sistem kerahasiaan disebut kriptologi. Kriptografi merupakan bagian dari kriptologi yang berhubungan dengan desain dan implementasi sistem kerahasiaan, sedangkan kriptanalisis bertujuan melanggar sistem ini. Sebuah pesan yang akan diubah menjadi bentuk rahasia disebut plaintext. Cipher adalah metode untuk mengubah pesan plaintext menjadi ciphertext dengan mengubah huruf dari plaintext dengan menggunakan transformasi. Kuncinya menentukan transformasi tertentu dari satu set transformasi mungkin. Proses mengubah plaintext menjadi ciphertext disebut enkripsi atau enciphering, sedangkan proses kebalikan dari mengubah ciphertext kembali ke plaintext oleh penerima yang dituju, memiliki pengetahuan tentang metode melakukan hal ini, disebut dekripsi atau mengartikan. Ini, tentu saja, berbeda dari proses seseorang selain penerima yang dimaksudkan digunakan untuk membuat pesan dipahami melalui pembacaan sandi. Dalam bab ini, kami menyajikan sistem kerahasiaan berdasarkan aritmatika modular. Yang pertama itu berasal dengan Julius Caesar. Sistem kerahasiaan terbaru akan kita bahas ditemukan pada tahun 1970-an. Dalam semua sistem ini kita mulai dengan menerjemahkan huruf menjadi angka. Kami mengambil sebagai standar kami alfabet huruf bahasa Inggris dan menerjemahkan mereka ke dalam integer dari 0 ke 25, seperti yang ditunjukkan pada Tabel 7.1. Letter Numerical equvalent

A 0

B 1

C 2

D 3

E 4

F 5

G 6

H 7

I 8

J 9

K 10

L 11

M 12

N 13

O 14

P 15

Q 16

R 17

S 18

T 19

U 20

Table7 .1. Para numerik Setara Sastra Tentu saja, jika kita mengirim pesan Rusia, Yunani, Ibrani atau bahasa lain kita akan menggunakan berbagai bilangan bulat yang sesuai abjad. Juga, kita mungkin ingin memasukkan tanda baca, simbol untuk menunjukkan kosong, dan mungkin untuk mewakili digit nomor sebagai bagian dari pesan. Namun, demi kesederhanaan, kita membatasi diri pada huruf-huruf alfabet Inggris. Pertama, kita bahas berdasarkan sistem kerahasiaan mengubah setiap huruf dari pesan plaintext menjadi huruf yang berbeda untuk menghasilkan ciphertext. Cipher seperti ini disebut cipher karakter atau monografi, karena Pendidikan Matematika FKIP UMB-Yogyakarta

Page 58

V 21

W 22

X 23

Y 24

setiap huruf berubah secara individu untuk surat lain dengan substitusi. Secara keseluruhan, ada 26! cara yang mungkin untuk menghasilkan transformasi monografi. Kita akan membahas satu set yang didasarkan pada aritmatika modula. Sebuah cipher, yang digunakan oleh Julius Caesar, didasarkan pada substitusi di mana setiap huruf digantikan dengan huruf tiga bagian bawah abjad, dengan tiga huruf terakhir bergeser ke tiga huruf pertama dari alfabet. Untuk menggambarkan cipher ini menggunakan aritmatika modular, biarkan P menjadi setara numerik surat dalam plaintext dan C setara numerik dari huruf cipherteks yang sesuai. Kemudian

CP3Mod26,0C25

Korespondensi antara plaintext dan ciphertext diberikan dalam Tabel 7.2. Plaintext

A 0

B 1

C 2

D 3

E 4

F 5

G 6

H 7

I 8

J 9

K 10

L 11

M 12

N 13

O 14

P 15

Q 16

R 17

S 18

T 19

U 20

V 21

W 22

X 23

Y 24

Z 2

ciphertext

3 D

4 E

5 F

6 G

7 H

8 I

9 J

10 K

11 L

12 M

13 N

14 O

15 P

16 Q

17 R

18 S

19 T

20 U

21 V

22 W

23 X

24 Y

25 Z

0 A

1 B

2 C

Tabel 7 .2. The Korespondensi Surat untuk Cipher Caesar Untuk menulis dlm kode pesan menggunakan transformasi ini, pertama kita ubah ke setara numeriknya, pengelompokan huruf di blok lima. Kemudian kita mengubah setiap angka. Pengelompokan surat ke blok membantu mencegah kriptanalisis sukses berdasarkan mengenali kata-kata tertentu. Kami mengilustrasikan prosedur ini dengan enciphering pesan THIS MESSAGE IS TOP SECRET. Broken ke dalam kelompok lima huruf, pesan THISM ESSAG EISTO PSECR ET. Mengubah huruf menjadi setara numerik, kita memperoleh 19 7 8 18 12 4 18 18 0 6 4 8 18 19 14 15 18 4 2 17 4 19 Menggunakan transformasi Caesar CP3Mod 26 ini menjadi 22 10 11 21 15 7 21 21 3 9 7 11 21 22 17 18 21 7 5 20 7 22





Penerjemahan kembali ke huruf, kami telah WKLVP HVVDJ HLVWR SVHGU HW. Ini adalah pesan yang kami kirim. Penerima deciphers dalam cara sebagai berikut. Pertama, surat-surat dikonversi ke angka. Kemudian, hubungan CP3 Mod 26,0C25 digunakan untuk mengubah ciphertext kembali ke versi numerik plaintext, dan akhirnya pesan diubah menjadi huruf. Kami menggambarkan prosedur mengartikan dengan pesan berikut enciphered oleh sandi Caesar:






Page 59

WKLVL VKP.ZZ HGHFL SKHU. Pertama, kami mengubah huruf menjadi setara numerik mereka, untuk memperoleh 22 10 11 21 11 21 l0 17 25 25 7 6 7 5 11 18 10 7 20 . Selanjutnya, kita melakukan transformasi CP3Mod 26 untuk mengubah ini untuk plaintext, dan kami memperoleh 19 7 8 18 8 18 7 14 22 22 4 3 4 2 8 15 7 4 17.





Kami menerjemahkan ini kembali ke surat dan mengembalikan pesan plaintext THISI SHOWW EDECI PHER. Dengan menggabungkan huruf-huruf yang sesuai dengan kata-kata, kita menemukan bahwa pesan reads THIS IS HOW WE DECIPHER. Cipher Caesar adalah salah satu dari keluarga cipher serupa digambarkan oleh transformasi shft

CP3Mod26,0C25

di mana k adalah kunci yang mewakili ukuran pergeseran huruf dalam alfabet. Ada 26 transformasi yang berbeda dari jenis ini, termasuk kasus k = 0 (mod 26), di mana huruf tidak berubah, karena dalam hal ini CP Mad 26 . Secara umum, kami akan mempertimbangkan transformasi jenis ( 7.1 )





CaPbMod26,0C25

dimana a dan b adalah bilangan bulat dengan (a, 26) = 1. Ini disebut transformasi affine. Shift transformasi adalah transformasi affine dengan a=1 . Kami mengharuskan (a, 26) = 1, sehingga sebagai P berjalan melalui sistem residu lengkap modulo 26, C juga tidak. Ada 2612pilihan untuk a, dan 26 pilihan untuk b, memberikan total 1226312transformasi jenis ini (salah satunya adalah C = P (mod 26) diperoleh bila a = 1 dan b = 0. Jika reliationship antara plaintext dan ciphertext dijelaskan oleh (7.1), maka hubungan terbalik diberikan oleh

 

PaCbMad26,0P25

dimana merupakan kebalikan dari sebuah (mod 26) Sebagai contoh dari cipher, mari a = 7 dan b = 10, sehingga C7P10Mod26 Oleh karena itu, P15C10 15C6 Mod26 . sejak 15 adalah kebalikan dari 7 modulo 26. Korespondensi antara huruf diberikan dalam Tabel 7.3.







Plaintext

A 0

B 1

C 2

D E 3 4

F 5

G 6

ciphertext

10 K

17 R

24 Y

5 F

19 T

0 7 14 A H O

12 M

H I 7 8







J 9

K 10

L 11

M 12

N 13

O 14

P 15

Q 16

R 17

S 18

T 19

U 20

V 21

W 22

X 23

Y 24

21 V

2 C

9 J

16 Q

23 X

4 E

11 S

18 S

25 Z

6 G

13 N

20 U

1 B

8 I

15 P

22 W

Table 7 .3. The Korespondensi Surat untuk Cipher dengan Pendidikan Matematika FKIP UMB-Yogyakarta

Page 60

Untuk menggambarkan bagaimana kami memperoleh ini korespondensi, perhatikan bahwa huruf plaintext L dengan setara numerik 11 sesuai dengan huruf J ciphertext, 71110879 Mod 26 dan 9 adalah setara numerik J.





Untuk menggambarkan cara menulis dlm kode, perhatikan bahwa Contoh : PLEASE SEND MONEY dapat di rubah menjadi LJMKG MGMFQ EXMW. Pada chipertext FEXEN ZMBMK JNHMG MYZMN, sama dengan DONOT REVEA LTHES ECRET atau DO NOT REVEAL THE SECRET pada plaintext. Sekarang

kita membahas beberapa teknik

yang diarahkan pada

pembacaan sandi dari cipher berdasarkan transformasi affine. Dalam upaya memecahkan ipher monografi, frekuensi huruf dalam ciphertext dibandingkan dengan frekuensi pada teks biasa. Ini memberikan informasi mengenai kesesuaian antara huruf. Dalam perhitungan berbagai macam frekuensi pada teks English, salah satunya menemukan persentase yang terdapat dalam tabrl 7.4 untuk kejadian ke 26 huruf. letter Frequensi (%)

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

7

1

3

4

13

3

2

3

8

<1

<1

4

3

8

7

3

<1

8

6

9

3

1

1

<1

2

<1

Tabel 7.4. Frekuensi dari kejadian huruf pada alfabet. Dari tabel ini didapatkan bahwa frekuensi yang sering muncul pada teks English adalah E, T, N, R, I, O dan A. Kita dapat menggunkan informasi ini untuk membedakan chiper yang mana pada sebuah transformasi affine yang telah digunakan untuk menulis pesan. Contoh : Pendidikan Matematika FKIP UMB-Yogyakarta

Page 61

Dalam chipertext YFXMP

CESPZ

CJTDF

DPQFW

NTASP

CTYRX

PDDLR

PD

QZCPY

Pertama-tama dengan menghitung huruf yang muncul dalam chipertext, yaitu Letter Angka yang muncul

A B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

1 0

4

5

1

3

0

0

0

1

0

1

1

1

0

7

2

2

2

3

0

0

1

2

3

Dari tabel didapatkan bahwa huruf yang sering muncul : P, C, D, F, T dan Y. P menggambarkan huruf E karena E adalah huruf yang sering muncul dalam teks English. Jika demikian maka

.

Dan

, maka didapatkan kesamaan

A B C

D E F

G H I

J

0

1

2

3

4

5

6

7

8

9

plai

1

1

1

1

1

2

2

2

2

2

2

ntex

5

6

7

8

9

0

1

2

3

4

5

chip erte xt

t

P Q R S

K L

M N O P Q R S

T U V W X Y Z

1

1

1

1

1

1

1

1

1

1

2

2

2

2

2

2

0

1

2

3

4

5

6

7

8

9

0

1

2

3

4

5

0

1

2

3

4

5

6

7

8

9

1

1

1

1

1

0

1

2

3

4

G H I

J

T U V W X Y Z

A B C D E F

K L

M N O

Dari kesamaan ini maka YFXMP CESPZ CJTDF DPQFW QZCPY NTASP CTYRX PDDLR PD sama dengan NUMBE RTHEO RYISU SEFUL FOREN CIPHE RINGM ESSAG ES atau NUMBER THEORY IS USEFUL FOR ENCIPHERING MESSAGES. Akibatnya, kita membuat menebak benar. Jika kita telah mencobatransfo rmasi,

dan bukannya plaintext,


dan

menghasilkan teks kacau, maka akan

Page 62

mencoba transformasi lain mungkin berdasarkan jumlah frekuensi huruf dalam ciphertext. Transformasi affine dari bentuk

digunakan

dalam penerjemahan. Contoh :

letter

USLEL

JUTCC

YRTPS

URKLT

YGGFV

ELYUS

LRYXD

JURTU

ULVCU

URJRK

QLLQL

YXSRV

LBRYZ

CYREK

LVEXB

RYZDG

HRGUS

LJLLM

LYPDJ

LJTJU

FALGU

PTGVT

JULYU

SLDAL

TJRWU

SLJFE

OLPU

A B

C

D

E

F

G

H

I

2 2

4

4

5

3

6

1

0

J

Angka yang

K

1

M

N

O

P

Q

1

0

1

4

2

2

3

0

muncul

L

2

R 1 2

S

T

7

8

U 1 6

V

W

X

5

1

3

Y

Z

1

2

0

Dari tabel didapatkan huruf L adalah sering muncul dalam chipertext dan hal ini sama dengan huruf E. Sedang huruf U sama dengan T. Sehingga

Dengan torema 3.14 didapatkan

dan

Jika transformasinya benar, dan 19 adalah invers dari 11 modulo 26, maka ;

sehingga

di

dapatka

chipertext

plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

3

22

15

8

1

20

13

6

25

18

11

4

23

16

9

2

21

14

7

0

19

12

5

24

17

10

D

W

P

I

B

U

N

G

Z

S

L

E

X

Q

J

C

V

O

H

A

T

M

P

Y

R

K


Page 63

Maka USLEL

JUTCC

YRTPS

URKLT

YGGFV

ELYUS

LRYXD

JURTU

ULVCU

URJRK

QLLQL

YXSRV

LBRYZ

CYREK

LVEXB

RYZDG

HRGUS

LJLLM

LYPDJ

LJTJU

FALGU

PTGVT

JULYU

SLDAL

TJRWU

SLJFE

OLPU

Sama dengan THEBE

STAPP

ROACH

TOLEA

RNNUM

BERTH

EORYI

STOAT

TEMPT

TOSOL

VEEVE

RYHOM

EWORK

PROBL

EMBYW

ORKIN

GONTH

ESEEX

ERCIS

ESAST

UDENT

CANMA

STERT

HEIDE

ASOFT

HESUB

JECT


Page 64

BAHAN AJAR TEORI BILANGAN

Recommend Documents